**Drawings of planar graphs with few slopes and segments.**

V. Dujmović, D. Eppstein, M. Suderman, and D. R. Wood.

arXiv:math.CO/0606450.

*Comp. Geom. Theory & Applications*38: 194–212, 2007.We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most 5n/2 segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface).

**Structure of graphs with locally restricted crossings**.

V. Dujmović, D. Eppstein, and D. R. Wood.

arXiv:1506.04380.

*23rd Int. Symp. Graph Drawing*, Los Angeles, California, 2015.

Springer,*Lecture Notes in Comp. Sci.*9411 (2015), pp. 87–98.

*SIAM J. Discrete Math.*31 (2): 805–824, 2017.The Graph Drawing version used the alternative title "Genus, treewidth, and local crossing number". We prove tight bounds on the treewidth of graphs embedded on low-genus surfaces with few crossings per edge, and nearly tight bounds on the number of crossings per edge for graphs with a given number of edges embedded on low-genus surfaces.

(Slides -- local copy of final version)

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

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.