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⊆H⊠P⊠Kmax{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ℓ, for some planar graph H with treewidth 3, where ℓ=max{2g⌊d2⌋,d+3⌊d2⌋−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⊠Kmax{4g,7}, for some planar graph H with treewidth 3.
Improved Product Structure for Graphs on Surfaces / Distel, M.; Hickingbotham, R.; Huynh, T.; Wood, D. R.. - In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE. - ISSN 1365-8050. - (2021). [10.48550/arXiv.2112.10025]
Improved Product Structure for Graphs on Surfaces
Huynh, T.;
2021
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⊆H⊠P⊠Kmax{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ℓ, for some planar graph H with treewidth 3, where ℓ=max{2g⌊d2⌋,d+3⌊d2⌋−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⊠Kmax{4g,7}, for some planar graph H with treewidth 3.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
