Short Paths in the Planar Graph Product Structure Theorem

Abstract

The Planar Graph Product Structure Theorem of Dujmović et al. [J. ACM '20] says that every planar graph $G$ is contained in $H⊠P⊠K_3$ for some planar graph $H$ with treewidth at most 3 and some path $P$. This result has been the key to solving several old open problems. Several people have asked whether the Planar Graph Product Structure Theorem can be proved with good upper bounds on the length of $P$. No $o(n)$ upper bound was previously known for $n$-vertex planar graphs. We answer this question in the affirmative, by proving that for any $\epsilon \in (0,1)$ every $n$-vertex planar graph is contained in $H⊠P⊠K_{O(1/\epsilon )}$, for some planar graph $H$ with treewidth 3 and for some path $P$ of length $O(\frac{1}{\epsilon }{n}^{(1+\epsilon )/2})$. This bound is almost tight since there is a lower bound of $\Omega (n^{1/2})$ for certain $n$-vertex planar graphs. In fact, we prove a stronger result with $P$ of length $O(\frac{1}{\epsilon }\text{tw}(G)n^{\epsilon })$, which is tight up to the $O(\frac{1}{\epsilon }{n}^{\epsilon })$ factor for every $n$-vertex planar graph $G$. Finally, taking $\epsilon =\frac{1}{\log n}$, we show that every $n$-vertex planar graph $G$ is contained in $H⊠P⊠K_{O(\log n)}$ for some planar graph $H$ with treewidth at most 3 and some path $P$ of length $O(\text{tw}(G)\log n)$. This result is particularly attractive since the treewidth of the product $H⊠P⊠K_{O(\log n)}$ is within a $O({\log }^{2}n)$ factor of the treewidth of $G$.

21 pages, 1 figure