**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.

**Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth**.

M. J. Bannister and D. Eppstein.

arXiv:1408.6321.

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

Springer,*Lecture Notes in Comp. Sci.*8871, 2014, pp. 210–221.We show how to express in monadic second-order logic the problems of drawing a graph with a fixed number of crossings on a one or two page book layout. By applying Courcelle's theorem, we obtain fixed-parameter tractable algorithms for these problems, parameterized by treewidth.

**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.

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

Semi-automatically filtered from a common source file.