Layered Partitions of $k$-Planar Graphs
Pat Morin
Carleton University

Layered $H$-partitions of graphs (with small layered width, in which $H$ has small treewidth) are a recently-introduced tool that have been used to solve longstanding problems on queue layouts, non-repetitive colouring, and 3-d graph drawing. Such partitions are known to exist for planar graphs and, more generally, bounded genus graphs. In the current paper, we prove that every $k$-planar graph has a layered $H$-partition of layered width $O(k^2)$ in which $H$ has treewidth $O(k^3)$. This is the first result of this type for a non-minor-closed class of graphs and implies that $k$-planar graphs have both queue number and non-repetitive chromatic number upper-bounded by a function of $k$. The former result was previously shown using a combination of $H$-partitions for planar graphs with \textit{ad hoc} methods. The latter result is new, for all $k\ge 1$. These results extend to $(g,k)$-planar graphs, the natural generalization of $k$-planar graphs to to genus-$g$ surfaces (rather than the genus-$0$ plane).