Planar graphs in blowups of fans

Planar graphs, which are graphs that can be embedded in the plane without edge crossings, are of fundamental importance in both structural and algorithmic graph theory. A classical result on the structure of planar graphs is the Planar Separator Theorem of Lipton and Tarjon, which states that every \(n\)-vertex planar graph contains a set of \(O(\sqrt{n})\) vertices whose removal breaks the graph into connected components of size at most \(2n/3\). Among its many applications, one can find constructions of small universal graphs for planar graphs and the design of efficient divide and conquer algorithms for planar inputs.

Recently, a new insight into the structure of planar graphs was provided by the Planar Graph Product Structure Theorem, which was proven by Dujmović, Joret, Micek, Morin, Ueckerdt and Wood in 2020. The theorem states that every planar graph is a subgraph of the strong product of a graph with bounded tree-width and a path. This product can be thought of as a tree-like grid and so the result highlights the intrinsically two-dimensional nature of planar graphs. The main result of the present paper states that every \(n\)-vertex planar graph, and more generally every \(n\)-vertex graph in a fixed minor-closed class of graphs, embeds as a subgraph into the strong product of a fan and a complete graph with \(O(\sqrt{n}\log^2 n)\) vertices. In other words, these graphs admit a path-like (one dimensional) clustering given by the linearly ordered \(O(\sqrt{n}\log^2 n)\)-vertex separators exhibited by this embedding.