3
$\begingroup$

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$).

Improve this question
$\endgroup$
4
  • $\begingroup$ Maybe you want to formulate the question in a more precise way? For some $G$ and $N$ it is possible, and for some not. $\endgroup$
    – Anton Petrunin
    Commented Sep 22, 2022 at 14:27
  • $\begingroup$ @AntonPetrunin I added some clarification and details; but generally, I'm looking for conditions on G for when this can happen. $\endgroup$
    – ABIM
    Commented Sep 22, 2022 at 15:37
  • $\begingroup$ An easy condition would be too much to expect. Even for $N=2$. $\endgroup$
    – Anton Petrunin
    Commented Sep 22, 2022 at 16:08
  • $\begingroup$ @AntonPetrunin Oh by "easy condition" I mean perhaps a simple class of graphs G admitting such a decomposition $\endgroup$
    – ABIM
    Commented Sep 22, 2022 at 16:18

1 Answer 1

Reset to default
4
$\begingroup$

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.

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

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Wow amazing answer! Thanks so much; this seems to be exactly what I was looking for (+ more since it has nice background + history) thanks a million :) $\endgroup$
    – ABIM
    Commented Sep 22, 2022 at 16:47
  • $\begingroup$ Also are there quantitative estimates on the number N? $\endgroup$
    – ABIM
    Commented Sep 22, 2022 at 21:15
  • 1
    $\begingroup$ That's a good question. The proof is constructive, but I think the bounds on N can be quite bad. See arxiv.org/abs/2202.08870 for an algorithm that computes the decomposition. $\endgroup$
    – Tony Huynh
    Commented Sep 23, 2022 at 9:43
  • 1
    $\begingroup$ For your now (deleted) question, such a partition is sometimes called a layered partition, since the parts can actually be chosen to be 'vertical paths' from a fixed BFS spanning tree. Thus, each part intersects each 'layer' of the tree at most once. $\endgroup$
    – Tony Huynh
    Commented Sep 23, 2022 at 9:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .