Publications with Robert Hickingbotham
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, doi:10.1007/s00493-021-4585-7.
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, doi:10.1007/s00454-022-00478-6.
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, doi:10.1137/23M1591773.
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.