An Improved Planar Graph Product Structure Theorem
Torsten Ueckerdt, David R. Wood, Wendy Yi
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\subseteq H\boxtimes P$. We improve this result by replacing "treewidth at most 8" by "simple treewidth at most 6".
Topics & Concepts
TreewidthMathematicsCombinatoricsPlanar graphGraphPartial k-treeOuterplanar graphPolyhedral graphDiscrete mathematicsGraph minor1-planar graphProduct (mathematics)PathwidthLine graphGraph powerGeometryAdvanced Graph Theory ResearchComputational Geometry and Mesh GenerationComplexity and Algorithms in Graphs