David Eppstein - Publications

To appear with unknown date

• 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., to appear.
  

  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.

• Orthogonal dissection into few rectangles.
  D. Eppstein.
  arXiv:2206.10675.
  34th Canadian Conference on Computational Geometry, 2022, pp. 143–150.
  Discrete Comput. Geom., to appear.
  

  The rank of the Dehn invariant of an orthogonal polygon equals the minimum number of rectangles into which it can be transformed by axis-parallel cuts, translation, and gluing. This allows the minimum number of rectangles to be calculated in polynomial time.

  (Slides)

• 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., to appear.
  

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

Semi-automatically filtered from a common source file.