Let $G=(V,E)$ be a finite undirected graph which we equip with its usual graph *geodesic distance* $d\_G$ making $(G,d\_G)$ into a metric space; let $1<\#V<\infty$. For a given $1<N< \#V$ *what conditions do I need* on $G$ so that does there exist *disjoint* subsets $V\_1,\dots,V\_N\subseteq V$ such that


* $\biguplus\_{n=1}^N\, V\_n = V$,
* $d\_{(V\_n,E\_n)}(x,y)=d\_{G}(x,y)$ for every $x,y\in V\_n$,


Here $E\_n:=\{(v,w):\,v,w\in V\_n\}$ *denotes the collection of edges connecting any two vertices in the "part" $V\_n$* and where $d\_{(V\_n,E\_n)}$ denotes the graph geodesic defined on the graph $(V\_n,E\_n)$ *(note, for arbitrary choices of $\{V\_n\}\_{n=1}^N$ we always have $d\_{(V\_n,E\_n)}\ge d\_G$)*.



"Geodesic coherent" partition of a graph
[Pilipczuk and Siebertz](https://arxiv.org/abs/1807.03683) 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](https://en.wikipedia.org/wiki/Treewidth) at most 8. This result was strengthened by [Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood](https://arxiv.org/abs/1904.04791), who proved that every planar graph is a subgraph of the [strong product](https://en.wikipedia.org/wiki/Strong_product_of_graphs) 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](https://arxiv.org/abs/2001.08860) and the references therein for more information.


**Disclaimer.** I am one of the authors of the above survey.


