Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure

Product structure theorems are a collection of recent results that have been used to resolve a number of longstanding open problems on planar graphs and related graph classes. One particularly useful version states that every planar graph G is contained in the strong product of a $3$-tree H, a path P, and a $3$-cycle K₃; written as G⊆ H P K₃. A number of researchers have asked if this theorem can be strengthened so that the maximum degree in H can be bounded by a function of the maximum degree in G. We show that no such strengthening is possible. Specifically, we describe an infinite family G of planar graphs of maximum degree $5$ such that, if an n-vertex member G of G is isomorphic to a subgraph of H P Kc where P is a path and H is a graph of maximum degree Δ and treewidth t, then tΔ c ≥ 2Ω(√loglog n).