Movatterモバイル変換

Marc Distel ; Robert Hickingbotham ; Tony Huynh ; David R. Wood -Improved product structure for graphs on surfaces

Authors: Marc Distel ; Robert Hickingbotham; Tony Huynh; David R. Wood

Dujmovi\'c, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved thatfor every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth atmost 4 and a path $P$ such that $G\subseteq H \boxtimes P \boxtimesK_{\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 framedgraphs. This implies that every $(g,d)$-map graph is contained in $ H \boxtimesP\boxtimes 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\}$. Italso implies that every $(g,1)$-planar graph (that is, graphs that can be drawnin a surface of Euler genus $g$ with at most one crossing per edge) iscontained in $H\boxtimes P\boxtimes K_{\max\{4g,7\}}$, for some planar graph$H$ with treewidth $3$.

Classifications

• 05C60 - Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
• 05C76 - Graph operations (line graphs, products, etc.)