eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2022-10-21
vol. 24, no 2
Graph Theory
10.46298/dmtcs.8877
8877
journal article
Improved product structure for graphs on surfaces
Marc Distel
Robert Hickingbotham
Tony Huynh
David R. Wood
Dujmovi\'c, 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 \boxtimes P \boxtimes
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 \boxtimes
P\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\}$. 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\boxtimes P\boxtimes K_{\max\{4g,7\}}$, for some planar graph
$H$ with treewidth $3$.
https://dmtcs.episciences.org/8877/pdf
Mathematics - Combinatorics