TY - JOUR
T1 - Improved Product Structure for Graphs on Surfaces
AU - Distel, Marc
AU - Hickingbotham, Robert
AU - Huynh, Tony
AU - Wood, David R.
N1 - Funding Information:
∗Research of M.D. and R.H. is supported by an Australian Government Research Training Program Scholarship. Research of T.H. and D.W. is supported by the Australian Research Council. (i) A plane graph is a graph embedded in the plane with no crossings. A plane triangulation is a plane graph in which every face is bounded by a triangle (that is, has length 3). A plane near-triangulation is a plane graph, where the outer-face is a cycle, and every internal face is a triangle. (ii)FortwographsGandH,thestrongproductG Histhegraphwithvertex-setV(G)×V(H)andanedgebetweentwovertices (v,w)and(v′,w′)ifandonlyifv=v′andww′∈E(H),orw=w′andvv′∈E(G),orvv′∈E(G)andww′∈E(H). (iii) A tree-decomposition of a graph G is a collection (Bx ⊆ V (G) : x ∈ V (T )) of subsets of V (G) (called bags) indexed by the nodes of a tree T, such that (a) for every edge uv ∈ E(G), some bag Bx contains both u and v, and (b) for every vertex v ∈ V (G), the set{x ∈ V (T ) : v ∈ Bx} induces a non-empty subtree of T . The width of a tree-decomposition is the size of a largest bag minus 1. The treewidth of a graph G, denoted by tw(G), is the minimum width of a tree-decomposition of G. Treewidth is recognised as the most important measure of how similar a given graph is to a tree. (iv) A graph G is contained in a graph X if G is isomorphic to a subgraph of X. A multigraph G is contained in a graph X if the simple graph underlying G is contained in X.
Publisher Copyright:
© 2022 by the author(s)
PY - 2022/10/21
Y1 - 2022/10/21
N2 - 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⌊d/2⌋, d + 3⌊d/2⌋ - 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.
AB - 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⌊d/2⌋, d + 3⌊d/2⌋ - 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.
KW - graphs on surfaces
KW - product structure
UR - http://www.scopus.com/inward/record.url?scp=85142118623&partnerID=8YFLogxK
U2 - 10.46298/dmtcs.8877
DO - 10.46298/dmtcs.8877
M3 - Article
AN - SCOPUS:85142118623
SN - 1365-8050
VL - 24
JO - Discrete Mathematics and Theoretical Computer Science
JF - Discrete Mathematics and Theoretical Computer Science
IS - 2
M1 - 6
ER -