3
$\begingroup$

I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in the plane so that the boundary of every face is a triangle. They construct a cycle $C$ on vertices $v_0, \ldots , v_{2k-1}$ such that when $D$ denotes the subgraph of $G$ induced by $C$ and the vertices on the inside of $G$ (in the fixed drawing), $C$ is geodesic in $D$: For any two vertices of $C$, their distance in $D$ is the same as in $C$. Then they say

There are $k+1$ vertex-disjoint paths of $D$ between $\{ v_0, \ldots, v_k \}$ and $\{ v_k, \ldots, v_{2k-1}, v_0 \}$. For otherwise, by a well-known form of Menger's Theorem for planar triangulations, there is a path of $D$ between $v_0$ and $v_k$ with $\leq k$ vertices.

What's more, they take these paths $P_0, \ldots, P_{k}$ so that $P_i$ joins $v_i$ to $v_{2k-i}$.

Unfortunately, I do not know the mentioned "form of Menger's Theorem for planar triangulations" and do not see how to derive it, given that it appears to include the notion of distances and provides a linkage from each $v_i$ to $v_{2k-i}$. A search on google has also not been successful.

Does anybody know the statement they refer to? Has it appeared somewhere explicitly? If not, can someone indicate how to prove it?

$\endgroup$
2
$\begingroup$

The standard version of Menger's theorem says that in any finite graph, the maximum number of vertex-independent paths between two vertices $a$ and $b$ is the same as the size of the smallest vertex cut separating $a$ and $b$. (Two paths are vertex-independent if they share no vertices except for their endpoints.)

Add two vertices $a$ and $b$ to your graph $D$ and connect $a$ to $v_0,\ldots, v_k$ and connect $b$ to $v_k,\ldots,v_{2k-1},v_0$, to get a new graph $D^+$, with a triangulated planar drawing. If we know that every vertex cut separating $a$ and $b$ has size at least $k+1$, we get by Menger's theorem a collection of $k+1$ vertex-independent paths from $a$ to $b$. Clearly, each of these paths should start by going from $a$ to $v_i$ (for some $i\in\{0,1,\ldots,k\}$) and end by going from $v_j$ (for some $j\in\{k,\ldots,2k-1,0\}$) to $b$. The planar drawing ensures that the path starting with $v_i$ ends with $v_j$ with $j=2k-i$ (where $2k=0$), hence you get your desired paths $P_0,\ldots,P_k$.

Let $\Lambda$ be a minimal vertex cut separating $a$ and $b$, so that $a$ and $b$ are in distinct connected components of $D^+\setminus\Lambda$. Clearly, $\Lambda$ must contain $v_0$ and $v_k$. By planarity, there is a Jordan curve $\gamma$ surrounding the component of $a$ in $D^+\setminus\Lambda$, separating it from the rest of the graph $D^+$. Let $e_1,e_2,\ldots,e_m$ be the edges from $D^+$ that are cut by $\gamma$, ordered according to $\gamma$, and such that $e_1$ is connected to $v_0$ and $e_m$ is connected to $v_k$. In particular, each $e_\ell$ has one endpoint in the component of $a$ in $D^+\setminus\Lambda$ and the other endpoint in $\Lambda$. Since the drawing of $D^+$ is triangulated, the edges $e_\ell$ and $e_{\ell+1}$ must be incident to each other and form a triangle with another edge in $D^+$. It follows that $\Lambda$ induces a path from $v_0$ to $v_k$. Since $C$ is geodesic in $D$, we know that there is no path in $D$ between $v_0$ and $v_k$ having less than $k+1$ vertices, so $\Lambda$ must contain at least $k+1$ vertices.

$\endgroup$
  • $\begingroup$ Very nice proof! Did you see that argument somewhere before or did you come up with it on the spot? (I'll leave the question open for a while to encourage pointers to the literature.) $\endgroup$ – monkeymaths Mar 21 '16 at 9:35
  • $\begingroup$ I don't work on this area, so I cannot give you a reference. I got the idea partly from this post, but someone working with planar triangulations might be more used to such arguments. So, I wouldn't be surprised if you cannot find an explicit proof written anywhere. $\endgroup$ – Algernon Mar 21 '16 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.