Improved product structure for graphs on surfaces

Abstract

Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth at most 4 and a path $P$ such that $G\subseteq H⊠P⊠K_{\max \{2g,3\}}$. We improve this result by replacing "4" by "3" and with $H$ planar. We in fact prove a more general result in terms of so-called framed graphs. This implies that every $(g,d)$-map graph is contained in $H⊠P⊠K_{\ell }$, for some planar graph $H$ with treewidth $3$, where $\ell =\max \{2g\lfloor \frac{d}{2}\rfloor ,d+3\lfloor \frac{d}{2}\rfloor -3\}$. It also implies that every $(g,1)$-planar graph (that is, graphs that can be drawn in a surface of Euler genus $g$ with at most one crossing per edge) is contained in $H⊠P⊠K_{\max \{4g,7\}}$, for some planar graph $H$ with treewidth $3$.

References in corpus (7)

• An annotated bibliography on 1-planarity
• Layered Separators in Minor-Closed Graph Classes with Applications
• Adjacency Labelling for Planar Graphs (and Beyond)
• Improved bounds for centered colorings
• Clustered 3-Colouring Graphs of Bounded Degree
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• Graph product structure for non-minor-closed classes

Cited by in corpus (2)

• Product structure of graphs with an excluded minor
• Colouring Strong Products