An improved planar graph product structure theorem

DOI10.37236/10614MaRDI QIDQ6374198arXivWikidataFDO

Authors Torsten Ueckerdt, David R. Wood, Wendy Yi

Publication date 31 July 2021

Published in arXiv

Full work available at URL https://doi.org/10.37236/10614

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

arXiv classification

cs.DMmath.CO

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 $$. We improve this result by replacing "treewidth at most 8" by "simple treewidth at most 6".

This page was built for publication: An improved planar graph product structure theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6374198)