Return to Revisions

Pilipczuk and Siebertz proved that every planar graph has such a partition with an even stronger property. Namely, each part $V_i$ is a geodesic path, and the graph obtained by contracting each part has treewidth at most 8. This result was strengthened by Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood, who proved that every planar graph is a subgraph of the strong product of a graph of treewidth at most 8 and a path. This theorem is now known as the Planar Graph Product Structure Theorem and has been the key tool in settling several long standing open problems on planar graphs. Similar partitions exist for other graph classes (beyond planar). Determining which graph classes admit a product structure theorem is now a very active research area. As a start, see this survey and the references therein for more information.