**Parameterized complexity of 1-planarity**.

M. J. Bannister, S. Cabello, and D. Eppstein.

arXiv:1304.5591.

13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario

Springer,*Lecture Notes in Comp. Sci. 8037*, 2013, pp. 97–108.

We show that testing whether a graph is 1-planar (drawable with at most one crossing per edge) may be performed in polynomial and fixed-parameter tractable time for graphs of bounded circuit rank, vertex cover number, or tree-depth. However, it is NP-complete for graphs of bounded treewidth, pathwidth, or bandwidth.

(Slides)

**Convex-arc drawings of pseudolines**.

D. Eppstein, M. van Garderen, B. Speckmann, and T. Ueckerdt.

*21st Int. Symp. Graph Drawing*(poster), Bordeaux, France, 2013.

Springer,*Lecture Notes in Comp. Sci.*8242, 2013, pp. 522–523.

arXiv:1601.06865.

We show that every outerplanar weak pseudoline arrangement (a collection of curves topologically equivalent to lines, each crossing at most once but possibly zero times, with all crossings belonging to an infinite face) can be straightened to a hyperbolic line arrangement. As a consequence such an arrangement can also be drawn in the Euclidean plane with each pseudoline represented as a convex piecewise-linear curve with at most two bends. In contrast, for arbitrary pseudoline arrangements, a linear number of bends is sufficient and sometimes necessary.

**Flat foldings of plane graphs with prescribed angles and edge lengths**.

Z. Abel, E. Demaine, M. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.

arXiv:1408.6771.

*22nd Int. Symp. Graph Drawing*, Würzburg, Germany, 2014.

Springer,*Lecture Notes in Comp. Sci.*8871, 2014, pp. 272–283.Given a plane graph with fixed edge lengths, and an assignment of the angles 0, 180, and 360 to the angles between adjacent edges, we show how to test whether the angle assignment can be realized by an embedding of the graph as a flat folding on a line. As a consequence, we can determine whether two-dimensional cell complexes with one vertex can be flattened. The main idea behind the result is to show that each face of the graph can be folded independently of the other faces.

**Track layouts, layered path decompositions, and leveled planarity**.

M. J. Bannister, W. E. Devanny, and V. Dujmović, D. Eppstein, and D. R. Wood.

arXiv:1506.09145.

*24th Int. Symp. Graph Drawing*, Athens, Greece, 2016.

Springer,*Lecture Notes in Comp. Sci.*9801 (2016), pp. 499–510.We introduce the concept of a layered path decomposition, and show that the layered pathwidth can be used to characterize the leveled planar graphs. As a consequence we show that finding the minimum number of tracks in a track layout of a given graph is NP-complete. The GD version includes only the parts concerning track layout, and uses the title "Track Layout is Hard".

**Maximum plane trees in multipartite geometric graphs**.

A. Biniaz, P. Bose, J.-L. De Carufel, K. Crosbie, D. Eppstein, A. Maheshwari, M. Smid.

15th Algorithms and Data Structures Symp. (WADS 2017), St. John's, Newfoundland.

Springer,*Lecture Notes in Comp. Sci.*(2017), pp. 193–204.We consider problems of constructing the maximum-length plane (non-self-crossing) spanning tree on Euclidean graphs given by multicolored point sets, where each point forms a vertex, and each bichromatic pair of points forms an edge with length equal to their Euclidean distance. We show that several such problems can be efficiently approximated.

**Triangle-free penny graphs: degeneracy, choosability, and edge count**.

D. Eppstein.

arXiv:1708.05152.

*Proc. 25th Int. Symp. Graph Drawing*, Boston, Massachusetts, 2017.

Springer,*Lecture Notes in Comp. Sci.*, to appear.A penny graph is the contact graph of unit disks: each disk represents a vertex of the graph, no two disks can overlap, and each tangency between two disks represents an edge in the graph. We prove that, when this graph is triangle free, its degeneracy is at most two. As a consequence, triangle-free penny graphs have list chromatic number at most three. We also show that the number of edges in any such graph is at most 2

*n*− Ω(√*n*).(Slides)

**The effect of planarization on width**.

D. Eppstein.

arXiv:1708.05155.

*Proc. 25th Int. Symp. Graph Drawing*, Boston, Massachusetts, 2017.

Springer,*Lecture Notes in Comp. Sci.*, to appear.We study what happens to nonplanar graphs of low width (for various width measures) when they are made planar by replacing crossings by vertices. For treewidth, pathwidth, branchwidth, clique-width, and tree-depth, this replacement can blow up the width from constant to linear. However, for bandwidth, cutwidth, and carving width, graphs of bounded width stay bounded when we planarize them.

(Slides)

Journals – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.