10.46298/dmtcs.8877
https://dmtcs.episciences.org/8877
Distel, Marc
Marc
Distel
Hickingbotham, Robert
Robert
Hickingbotham
Huynh, Tony
Tony
Huynh
Wood, David R.
David R.
Wood
Improved product structure for graphs on surfaces
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$.
episciences.org
Mathematics - Combinatorics
arXiv.org - Non-exclusive license to distribute
2022-09-26
2022-10-21
2022-10-21
eng
journal article
arXiv:2112.10025
10.48550/arXiv.2112.10025
1365-8050
https://dmtcs.episciences.org/8877/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
vol. 24, no 2
Graph Theory
Researchers
Students