An Improved Planar Graph Product Structure Theorem

Torsten Ueckerdt; David R. Wood; Wendy Yi

doi:10.37236/10614

An Improved Planar Graph Product Structure Theorem

Torsten Ueckerdt, David R. Wood, Wendy Yi

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-review

24 Citations (Scopus)

Abstract

Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every planar graph G there is a graph H with treewidth at most 8 and a path P such that G ⊆ H ⊠ P. We improve this result by replacing “treewidth at most 8” by “simple treewidth at most 6”.

Original language	English
Article number	P2.51
Number of pages	12
Journal	The Electronic Journal of Combinatorics
Volume	29
Issue number	2
DOIs	https://doi.org/10.37236/10614
Publication status	Published - 2022

Access to Document

10.37236/10614Licence: CC BY

Cite this

@article{f726852faa534d4b9b11edd553d53a78,

title = "An Improved Planar Graph Product Structure Theorem",

abstract = "Dujmovi{\'c}, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every planar graph G there is a graph H with treewidth at most 8 and a path P such that G ⊆ H ⊠ P. We improve this result by replacing “treewidth at most 8” by “simple treewidth at most 6”.",

author = "Torsten Ueckerdt and Wood, \{David R.\} and Wendy Yi",

note = "Funding Information: ∗Research supported by the Australian Research Council. Publisher Copyright: {\textcopyright} The authors.",

year = "2022",

doi = "10.37236/10614",

language = "English",

volume = "29",

journal = "The Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "2",

}

TY - JOUR

T1 - An Improved Planar Graph Product Structure Theorem

AU - Ueckerdt, Torsten

AU - Wood, David R.

AU - Yi, Wendy

N1 - Funding Information: ∗Research supported by the Australian Research Council. Publisher Copyright: © The authors.

PY - 2022

Y1 - 2022

N2 - Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every planar graph G there is a graph H with treewidth at most 8 and a path P such that G ⊆ H ⊠ P. We improve this result by replacing “treewidth at most 8” by “simple treewidth at most 6”.

AB - Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every planar graph G there is a graph H with treewidth at most 8 and a path P such that G ⊆ H ⊠ P. We improve this result by replacing “treewidth at most 8” by “simple treewidth at most 6”.

UR - https://www.scopus.com/pages/publications/85132939600

U2 - 10.37236/10614

DO - 10.37236/10614

M3 - Article

AN - SCOPUS:85132939600

SN - 1077-8926

VL - 29

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

IS - 2

M1 - P2.51

ER -

An Improved Planar Graph Product Structure Theorem

Abstract

Access to Document

Other files and links

Cite this