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

dmtcs:8877 - Discrete Mathematics & Theoretical Computer Science, October 21, 2022, vol. 24, no 2 - https://doi.org/10.46298/dmtcs.8877
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 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$.


    Volume: vol. 24, no 2
    Section: Graph Theory
    Published on: October 21, 2022
    Accepted on: September 26, 2022
    Submitted on: December 21, 2021
    Keywords: Mathematics - Combinatorics

    Share

    Consultation statistics

    This page has been seen 156 times.
    This article's PDF has been downloaded 116 times.