Graph product structure for non-minor-closed classes

Abstract

Dujmović et al. [\emph{J.~ACM}~'20] recently proved that every planar graph is isomorphic to a subgraph of the strong product of a bounded treewidth graph and a path. Analogous results were obtained for graphs of bounded Euler genus or apex-minor-free graphs. These tools have been used to solve longstanding problems on queue layouts, non-repetitive colouring, $p$-centered colouring, and adjacency labelling. This paper proves analogous product structure theorems for various non-minor-closed classes. One noteable example is $k$-planar graphs (those with a drawing in the plane in which each edge is involved in at most $k$ crossings). We prove that every $k$-planar graph is isomorphic to a subgraph of the strong product of a graph of treewidth $O(k^5)$ and a path. This is the first result of this type for a non-minor-closed class of graphs. It implies, amongst other results, that $k$-planar graphs have non-repetitive chromatic number upper-bounded by a function of $k$. All these results generalise for drawings of graphs on arbitrary surfaces. In fact, we work in a more general setting based on so-called shortcut systems, which are of independent interest. This leads to analogous results for certain types of map graphs, string graphs, graph powers, and nearest neighbour graphs.

v2 Cosmetic improvements and a corrected bound for (layered-)(tree)width in Theorems 2, 9, 11, and Corollaries 1, 3, 4, 6, 12. v3 Complete restructure. v4 Major revision, improved constants for 1-planar and d-map graphs. v5 Clarifications and corrections suggested by referee

Cited by in corpus (5)

• Stack-number is not bounded by queue-number
• Improved product structure for graphs on surfaces
• Tree densities in sparse graph classes
• Separating layered treewidth and row treewidth
• Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure