Treewidth 2 in the Planar Graph Product Structure TheoremArticle
Authors: Marc Distel ; Kevin Hendrey ; Nikolai Karol ; David R. Wood ; Jung Hon Yip
NULL##NULL##NULL##NULL##NULL
Marc Distel;Kevin Hendrey;Nikolai Karol;David R. Wood;Jung Hon Yip
We prove that every planar graph is contained in $H_1\boxtimes H_2\boxtimes
K_2$ for some graphs $H_1$ and $H_2$ both with treewidth 2. This resolves a
question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is
best possible: for any $c \in \mathbb{N}$, there is a planar graph $G$ such
that for any tree $T$ and graph $H$ with $\text{tw}(H) \leqslant 2$, $G$ is not
contained in $H \boxtimes T \boxtimes K_c$.