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.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.