David Eppstein - Publications

Publications with Michał T. Seweryn

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

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

Semi-automatically filtered from a common source file.