Bounded-degree planar graphs do not have bounded-degree product structure (Q6574390)

It is known that every planar graph \(G\) is contained in the strong product of a 3-tree \(H\), a path \(P\), and a 3-cycle \(K_3\); written as \(G \subseteq H \boxtimes P \boxtimes K_3\). Then a natural question that arises is: whether this result can be strengthened so that the maximum degree in \(H\) can be bounded by a function of the maximum degree in \(G\). \N\NIn this paper, the authors show that no such strengthening is possible. Specifically, the study describes an infinite family \(G\) of planar graphs of maximum degree 5 such that, if an \(n\)-vertex member \(G\) of \(\mathcal{G}\) is isomorphic to a subgraph of \(H \boxtimes P \boxtimes K_c\) where \(P\) is a path and \(H\) is a graph of maximum degree \(\Delta\) and treewidth \(t\), then \(t\Delta c\ge 2^{\Omega(\sqrt{\log \log n})}\).