David Eppstein - Publications

Publications with David R. Wood

• 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.
  Algorithmica 81 (4): 1561–1583, 2019.

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

• Minor-closed graph classes with bounded layered pathwidth.
  V. Dujmović, D. Eppstein, G. Joret, P. Morin, and D. R. Wood.
  arXiv:1810.08314.
  SIAM J. Discrete Math 34 (3): 1693–1709, 2020.

  A minor-closed graph family has a functional relation between diameter and path width (bounded local pathwidth) if and only if it excludes an apex-tree. The same graph families are also the ones with bounded layered pathwidth: a simultaneous path decomposition and layering (sequence of subsets of vertices with all edges connecting the same subset or consecutive subsets) so that the intersection of a bag and a layer has constant size.

• Stack-number is not bounded by queue-number.
  V. Dujmović, D. Eppstein, R. Robert Hickingbotham, P. Morin, and D. R. Wood.
  arXiv:2011.04195.
  Combinatorica 42: 151–164, 2022.

  Stack number is also known as page number or book thickness; it is the minimum number of stacks needed so that you can process the vertices of a graph in some sequence, pushing each edge onto one of the stacks when you process its first endpoint and popping it from the same stack when you process its second endpoint. Queue number is defined in the same way using queues instead of stacks. We show that the strong products of triangular grids and high-degree stars have bounded queue number but unbounded stack number. This result disproves the Blankenship–Oporowski conjecture, according to which subdividing edges of a graph a constant number of times cannot decrease its stack number from non-constant to constant, because subdivisions of the same products also have bounded stack number. It also confirms a conjecture of Bonnet et al on the existence of graphs with bounded sparse twin-width and unbounded stack number.

• Three-dimensional graph products with unbounded stack-number.
  D. Eppstein, R. Robert Hickingbotham, L. Merker, S. Norin, M. T. Seweryn, and D. R. Wood.
  arXiv:2202.05327.
  Discrete Comput. Geom. 71: 1210–1237, 2024.
  

  The strong product of any three graphs of non-constant size has unbounded book thickness. In the case of strong products of three paths, and more generally of triangulations of \(n\times n\times n\) grid graphs obtained by adding a diagonal to each square of the grid, the book thickness is \(\Theta(n^{1/3})\). This is the first explicit example of a graph family with bounded maximum degree and unbounded book thickness.

• Product structure extension of the Alon–Seymour–Thomas theorem.
  M. Distel, V. Dujmović, D. Eppstein, R. Robert Hickingbotham, G. Joret, P. Micek, P. Morin, M. T. Seweryn, and D. R. Wood.
  arXiv:2212.08739.
  SIAM J. Discrete Math. 38 (3): 2095–2107, 2024.
  

  The graphs in any nontrivial minor-closed graph family can be represented as strong products of a graph of treewidth 4 with a clique of size \(O(\sqrt{n})\). For planar graphs and \(K_{3,t}\)-minor-free graphs, the treewidth can be reduced to 2.