Separating a planar graph into two components containing shortest paths

131 Views Asked by At

Let $G$ be a planar graph containing more than 5 vertices (the choice of '5' is arbitrary, and a bigger minimum vertex number will do just fine). Is it always possible to find a vertex cut $S$ of $G$ such that the following properties hold?

  1. The cut separates $G$ into two non-empty and distinct components, $G_1$ and $G_2$.

  2. The set of shortest paths between two vertices $s,t$ in $G_i \cup S$ (for $i = 1,2$) is also the set of shortest paths between $s$ and $t$ in $G$

It is simple to see that in the case of a triangle no such cut exists (since one of $G_1$ or $G_2$ will necessarily be empty). The question, though, is whether it is guaranteed to exist for a large enough number of vertices.

Followup question: Is it always possible to separate a planar graph into two components $G_1$, $G_2$ via edge-cuts such that $G_i$ contains all shortest paths between two vertices of $G_i$?

1

There are 1 best solutions below

0
On BEST ANSWER

No.

Let's start with the second question. $K_{3,2}$ is a planar graph and either $G_1$ or $G_2$ will have to contain at least two vertices from the side of size 3. But then, to contain every shortest path it needs to include entire other side (of size two). That in turn implies it has to include whole side of size three as well, and the second subgraph is empty.

To answer your first question, similar thing happens only we use $G_1 \cup S$ and $G_2 \cup S$ instead. One union will have to contain at least two vertices from one side, and then the whole other side has to be included as well.

If you need graphs of bigger size, add $k$ dummy vertices of degree two on each edge (i.e. split each edge paths of length $k+1$).

I hope this helps $\ddot\smile$