A geometric proof of Okamura-Seymour

After using it in the last post on non-positively curved surfaces, I thought it might be nice to give a simple proof of the Okamura-Seymour theorem in the dual setting. This argument arose out of conversations in 2007 with Amit Chakrabarti and former UW undergrad Justin Vincent. I was later informed by Yuri Rabinovich that he and Ilan Newman discovered a similar proof.

Note that establishing a node-capacitated version of the Okamura-Seymour theorem was an open question of Chekuri and Kawarabayashi. Resolving it positively is somewhat more difficult.

Theorem 1 Given a weighted planar graph {G = (V,E)} and a face {F} of {G} , there is a non-expansive embedding {\varphi:V\rightarrow L_1} such that {\varphi|_F} is an isometry.

By rational approximation and subdivision of edges, we may assume that {G} is unweighted. The following proof is constructive, and provides an explicit sequence of cuts on {G} whose characteristic functions form the coordinates of the embedding {\varphi} . Each such cut is obtained by applying the following lemma. Note that for a subset {S} of vertices, we use the notation {G/\partial S} , for the graph obtained from {G} by contracting the edges across {S}

Lemma 2 (Face-preserving cut lemma) Let {G = (V,E)} be a {2} -connected bipartite planar graph and {F} be the boundary of a face of {G} . There exists a cut {S\subseteq V} such that

\displaystyle \forall\, u,v\in F,~ d_G(u,v) - d_{G/\partial S}(u,v) ~=~ |\mathbf{1}_S(u) - \mathbf{1}_S(v)| \, .

Proof: Fix a plane embedding of {G} that makes {F} the boundary of the outer face. Since {G} is {2} -connected, {F} is a cycle, and since {G} is bipartite and has no parallel edges, {\mathrm{len}(F)\geq 4} .

Consider an arbitrary pair {(a,b)} of distinct vertices on {F} . There is a unique path from {a} to {b} that runs along {F} counterclockwise; call this path {\lambda_{ab}} . Consider a path {\gamma\in\mathcal P_{ab}} and a vertex {w\in V} . We say that {w} lies below {\gamma} if, in the plane embedding of {G} , {w} lies in the closed subset of the plane bounded by {\gamma} and {\lambda_{ab}} .

(Note that the direction of {\gamma} is significant in the definition of “lying below,” i.e., belowness with respect to a path in {\mathcal P_{ab}} is not the same as belowness with respect to the reverse of the same path in {\mathcal P_{ba}} .)

We say that {w} lies strictly below {\gamma} if {w} lies below {\gamma} and {w\notin\gamma} . We use this notion of “lying below” to define a partial order on the paths in {\mathcal P_{ab}} : for {\gamma,\gamma'\in\mathcal P_{ab}} we say that {\gamma'} is lower than {\gamma} if every vertex in {\gamma'} lies below {\gamma} .

We now fix the pair {(a,b)} and a path {\pi\in\mathcal P_{ab}} so that the following properties hold:

  1. {\mathrm{len}(\pi) = d_G(a,b) < \mathrm{len}(\lambda_{ab})} .
  2. If {a',b'\in\lambda_{ab}} are distinct vertices with {a'} preceding {b'} and {d_G(a',b') < \mathrm{len}(\lambda_{a'b'})} , then {a' = a} and {b' = b} .
  3. If {\pi'\in\mathcal P_{ab}} is lower than {\pi} and {\mathrm{len}(\pi') = \mathrm{len}(\pi)} , then {\pi' = \pi} .

OKS cut

Note that a suitable pair {(a,b)} exists because {\mathrm{len}(F)\ge4} . Finally, we define the cut {S\subseteq V} as follows: {S = \{v\in V:\, v} does not lie strictly below {\pi\}} .

Claim 1 The cut {S} satisfies the conditions of the lemma.

For the rest of this section, we fix the pair {(a,b)} , the path {\pi} and the cut {S} as defined in the above proof.

Lemma 1 Let {x} and {y} be distinct vertices on {\pi} and {\beta\in\mathcal P_{xy}} be such that {\emptyset\ne\mathrm{int}(\beta)\subseteq\bar S} . Then {\mathrm{len}(\beta) - 2 \ge d_G(x,y)} .

Proof: If {x = y} the lemma holds trivially, so assume {x \ne y} . Also assume without loss of generality that {x} precedes {y} in the path {\pi} . The conditions on {\beta} imply that all vertices in {\mathrm{int}(\beta)} lie strictly below {\pi} . Therefore, the path {\pi' := \pi[a:x]\circ\beta\circ\pi[y:b]} is lower than {\pi} and distinct from {\pi}

By property (3), we have {\mathrm{len}(\pi') > \mathrm{len}(\pi)} , which implies {\mathrm{len}(\beta) > \mathrm{len}(\pi[x:y])} . Since {G} is bipartite, the cycle formed by {\beta} and {\pi[x:y]} must have even length; therefore, {\mathrm{len}(\beta) \ge \mathrm{len}(\pi[x:y]) + 2 = d_G(x,y) + 2} . \Box

Lemma 2 Let {x} and {y} be distinct vertices on {\pi} and {\gamma\in\mathcal P_{xy}} . Then {\mathrm{len}(\gamma) - |\gamma\cap\partial S| \ge d_G(x,y)} .

Proof: If {\gamma\cap\partial S = \emptyset} there is nothing to prove. If not, we can write

\displaystyle \gamma ~=~ \alpha_1 \circ \beta_1 \circ \alpha_2 \circ \beta_2 \circ \cdots \circ \alpha_k \circ \beta_k \circ \alpha_{k+1}

for some {k\ge1} where, for all {i} , {\alpha_i\subseteq S} and {\emptyset\ne\mathrm{int}(\beta_i)\subseteq \bar S} . Let {x_i} and {y_i} denote the endpoints of {\beta_i} with {x_i} preceding {y_i} in the path {\gamma} . Further, define {y_0 := x} and {x_{k+1} := y} .

By Lemma 1, we have {d_G(x_i,y_i) \le \mathrm{len}(\beta_i) - 2} for {1\le i\le k} . Since {\pi} is a shortest path, we have {d_G(y_{i-1},x_i) \le \mathrm{len}(\alpha_i)} for {1\le i\le k+1} . Therefore

\displaystyle d_G(x,y) ~\le~ \sum_{i=1}^k d_G(x_i,y_i) + \sum_{i=1}^{k+1} d_G(y_{i-1},x_i) ~\le~ \sum_{i=1}^k (\mathrm{len}(\beta_i) - 2) + \sum_{i=1}^{k+1} \mathrm{len}(\alpha_i)\,.

The latter quantity is precisely {\mathrm{len}(\gamma) - 2k}  which completes the proof since {|\gamma\cap\partial S| = 2k} . \Box

Proof of Claim 1: Let {u,v\in F} be arbitrary and distinct. It is clear that {d_{G/\partial S}(u,v) \le d_G(u,v) - |\mathbf{1}_S(u) - \mathbf{1}_S(v)|} , so it suffices to prove the opposite inequality. We begin by observing that

\displaystyle d_{G/\partial S}(u,v) ~=~ \min\left\{ \mathrm{len}(\gamma) - |\gamma\cap\partial S|:\, \gamma\in\mathcal P_{uv}\right\} \, .

Let {\gamma} be a path in {\mathcal P_{uv}} that achieves the minimum in the above expression. First, suppose {\gamma\cap\partial S = \emptyset} . Then we must have {\mathbf{1}_S(u) = \mathbf{1}_S(v)} . Now, {d_{G/\partial S}(u,v) = \mathrm{len}(\gamma) \ge d_G(u,v)} , which implies {d_{G/\partial S}(u,v) = d_G(u,v)} and we are done.

Next, suppose {\gamma\cap\partial S \ne \emptyset} . Then, there exists at least one vertex in {\gamma} that lies on {\pi} . Let {x} be the first such vertex and {y} the last (according to the ordering in {\gamma} ) and assume that {x} precedes {y} in the path {\pi} . Let {\hat\gamma := \gamma[x:y]} . Note that {\hat\gamma} may be trivial, because we may have {x = y} . Now, {\gamma\cap\partial S = (\gamma[u:x]\cap\partial S) \cup (\hat\gamma\cap\partial S) \cup (\gamma[y:v]\cap\partial S)} , whence

\displaystyle |\gamma\cap\partial S| ~=~ (1 - \mathbf{1}_S(u)) + |\hat\gamma\cap\partial S| + (1 - \mathbf{1}_S(v)) \, . \ \ \ \ \ (1)

 

This gives

{\displaystyle \begin{array}{rcl} d_{G/\partial S}(u,v) & = & \mathrm{len}(\gamma) - (1 - \mathbf{1}_S(u)) - |\hat\gamma\cap\partial S| - (1 - \mathbf{1}_S(v)) \\ &\geq & \mathrm{len}(\gamma[u:x]) + \mathrm{len}(\hat\gamma) + \mathrm{len}(\gamma[y:v]) + (\mathbf{1}_S(u) + \mathbf{1}_S(v) - 2) - |\hat\gamma\cap\partial S| \nonumber \\ &\geq & \mathrm{len}(\gamma[u:x]) + d_G(x,y) + \mathrm{len}(\gamma[y:v]) + (\mathbf{1}_S(u) + \mathbf{1}_S(v) - 2) \, \ \ \ \ \ (**) \\ &\geq & d_G(u,v) + (\mathbf{1}_S(u) + \mathbf{1}_S(v) - 2) \end{array}}

where the first line follows from Eq. (1) and the definition of {\gamma} and the third line is obtained by applying Lemma 2 to the path {\hat\gamma} . If at least one of {u,v} lies in {S} , then {\mathbf{1}_S(u) + \mathbf{1}_S(v) - 2 = -|\mathbf{1}_S(u) - \mathbf{1}_S(v)|} and we are done.

Therefore, suppose {u,v\in\bar S} . Let {\beta = \lambda_{ab}} . For a path {\alpha} and vertices {w,z} on {\alpha} , let us use {|wz|_\alpha} as shorthand for {\mathrm{len}(\alpha[w:z])} . By property (1), we have {|ab|_\beta > |ab|_\pi} and since {G} is bipartite, this means {|ab|_\beta - |ab|_\pi \ge 2} . By property (2), we have {d_G(u,b) = |ub|_\beta} and {d_G(a,v) = |av|_\beta} . Using these facts, we now derive

\displaystyle \begin{array}{rcl} \mathrm{len}(\gamma[u:x]) + d_G(x,y) + \mathrm{len}(\gamma[y:v]) & = & |ux|_\gamma + |xy|_\pi + |yv|_\gamma \\ & = & |ux|_\gamma + |xb|_\pi + |ay|_\pi + |yv|_\gamma - |ab|_\pi \\ &\ge& d_G(u,b) + d_G(a,v) - |ab|_\pi \\ & = & |ub|_\beta + |av|_\beta - |ab|_\pi \\ & = & |uv|_\beta + |ab|_\beta - |ab|_\pi \\ &\ge& |uv|_\beta + 2 \, . \end{array}

Using this in (**) above and noting that {\mathbf{1}_S(u) = \mathbf{1}_S(v) = 0} , we get {d_{G/\partial S}(u,v) \ge |uv|_\beta + 2 - 2 = d_G(u,v)} . This completes the proof. \Box

Proof of Theorem 1: Assume that {G} is {2} -connected. We may also assume that {G} is bipartite. To see why, note that subdividing every edge of {G} by introducing one new vertex per edge leaves the metric {d_G} essentially unchanged except for a scaling factor of {2} .

We shall now prove the stronger statement that for every face {f} of {G} there exists a sequence of cuts {S_1,S_2,\ldots,S_k} of {G} such that for all {u,v} on {f} , we have {d_G(u,v) = \sum_{i=1}^k |\mathbf{1}_{S_i}(u) - \mathbf{1}_{S_i}(v)|} and that for {i\ne j} , {\partial S_i\cap\partial S_j = \emptyset} . We prove this by induction on {|V|} .

The result is trivial in the degenerate case when {G} is a single edge. For any larger {G} and any cut {S\subseteq V} , the graph {G/\partial S} is either a single edge or is {2} -connected. Furthermore, contracting a cut preserves the parities of the lengths of all closed walks; therefore {G/\partial S} is also bipartite.

Apply the face-preserving cut lemma (Lemma 1) to obtain a cut {S_1\subseteq V} . By the above observations, we can apply the induction hypothesis to {G/\partial S_1} to obtain cuts {\hat S_2,\ldots,\hat S_k} of {G/\partial S_1} corresponding to the image of {f} in {G/\partial S_1} . Each cut {\hat S_i} induces a cut {S_i} of {G} . Clearly {\partial S_1\cap\partial S_i = \emptyset} for any {i > 1} . Finally, for any {u,v\in f} , we have

{\displaystyle d_G(u,v) = d_{G/\partial S_1}(u,v) + |\mathbf{1}_{S_1}(u) - \mathbf{1}_{S_1}(v)| = \sum_{i=2}^k |\mathbf{1}_{S_i}(u) - \mathbf{1}_{S_i}(v)| + |\mathbf{1}_{S_1}(u) - \mathbf{1}_{S_1}(v)|}

where the first equality follows from the property of {S_1} and the second follows from the induction hypothesis. This proves the theorem. \Box

Embeddings and extendable geodesics

Isometric embedding of non-positively curved surfaces into {L^1}

As I have mentioned before, one of my favorite questions is whether the shortest-path metric on a planar graph embeds into {L^1} with {O(1)} distortion. This is equivalent to such graphs having an {O(1)} -approximate multi-flow/min-cut theorem. We know that the distortion has to be at least 2. By a simple discretization and compactness argument, this is equivalent to the question of whether every simply-connected surface admits a bi-Lipschitz embedding into {L^1} .

In a paper of Tasos Sidiropoulos, it is proved that every simply-connected surface of non-positive curvature admits a bi-Lipschitz embedding into {L^1} . A followup work of Chalopin, Chepoi, and Naves shows that actually such a surface admits an isometric emedding into {L^1} . In this post, we present a simple proof of this result that was observed in conversations with Tasos a few years ago—it follows rather quickly from the most classical theorem in this setting, the Okamura-Seymour theorem.

Suppose that {(X,d)} is a geodesic metric space (i.e. the distance between any pair of points {x,y \in X} is realized by a geodesic whose length is {d(x,y)} ). One says that {(X,d)} has non-positive curvature (in the sense of Busemann) if for any pair of geodesics {\gamma : [a,b] \rightarrow X} and {\gamma' : [a',b'] \rightarrow X} , the map {D_{\gamma,\gamma'} : [0,1] \rightarrow \mathbb R} given by

\displaystyle  D_{\gamma,\gamma'}(t) = d\left(\vphantom{\bigoplus} \gamma((1-t)a + tb),\gamma'((1-t)a' + tb')\right)

is convex.

Theorem 1 Suppose that {\mathcal S} is homeomorphic to {\mathbb R^2} and is endowed with a geodesic metric {d} such that {(\mathcal S,d)} has non-positive curvature. Then {(\mathcal S,d)} embeds isometrically in {L^1} .

We will access the non-positive curvature property through the following fact. We refer to the book Metric spaces of non-positive curvature.

Lemma 2 Every geodesic {\gamma} in {\mathcal S} can be extended to a bi-infinite geodesic line.

Proof of Theorem 1: By a standard compactness argument, it suffices to construct an isometric embedding for a finite subset {X \subseteq \mathcal S} . Let {C} denote the convex hull of {X} . (A set {C} is convex if for every {x,y \in C} we have {\gamma \subseteq C} for every geodesic {\gamma} connecting {x} to {y} .)

Construction

It is an exercise to show that the boundary of {C} is composed of a finite number of geodesics {\mathcal F = \left\{[x_1, x_2], [x_2, x_3], \cdots, [x_{N-1},x_N], [x_N, x_1]\right\}} between points {x_1, x_2, \ldots, x_N \in C} . For every pair {x,y \in X} , let {\stackrel{\leftrightarrow}{xy}} denote a geodesic line containing {x} and {y} which exists by Lemma 2. Consider the collection of sets {\mathcal L = \mathcal F \cup \{ \stackrel{\leftrightarrow}{xy} : x,y \in X\}} , and let {I} denote the set of intersection points between geodesics in {\mathcal L} . Since {\mathcal L} is a collection of geodesics, and all geodesics intersect at most once (an easy consequence of non-positive curvature), the set {I} is finite.

Consider finally the set {Z = \{x_1, \ldots, x_N\} \cup X \cup I} . The geodesics in {\mathcal L} naturally endow {Z} with the structure of a planar graph {G=(Z,E)} , where two vertices {x,y \in Z} are adjacent if they lie on a subset of some geodesic in {\mathcal L} and the portion {[x,y]} between {x} and {y} does not contain any other points of {Z} . Note that {F = Z \cap \partial C} is the outer face of {G} in the natural drawing, where {\partial C} is the boundary of {C} (the union of the geodesics in {\mathcal F} ).

We can put a path metric on this graph by defining the length of an edge {\{x,y\}} as {d(x,y)} . Let {d_G} denote the induced shortest-path metric on the resulting graph. By construction, we have the following two properties.

  1. If {u,v \in X} or {u,v \in F\, \cap \stackrel{\leftrightarrow}{xy}} for some {x,y \in X} , then {d_G(u,v)=d(u,v)} .
  2. For every {x,y \in X} , there is a shortest path {P_{xy}} between two vertices in {F} such that {x,y \in P_{xy}} .

Both properties follow from our construction using the lines {\{ \stackrel{\leftrightarrow}{xy} : x,y \in X\}} .

Now let us state the geometric (dual) version of the Okamura-Seymour theorem.

Theorem 3 (Okamura-Seymour dual version) For every planar graph {G=(V,E)} and face {F \subseteq V} , there is a {1} -Lispchitz mapping {\varphi : V \rightarrow L^1} such that {\varphi|_F} is an isometry.

Let us apply this theorem to our graph {G} and face {F} . Consider {x,y \in X} and {\{u,v\} = F\, \cap \stackrel{\leftrightarrow}{xy}} . By property (1) above, we have {d_G(u,v)=d(u,v)} . Since {u,v \in F} , from Theorem 3, we have {\|\varphi(u)-\varphi(v)\|=d_G(u,v)} . But property (2) above says that {x} and {y} lie on a {u} {v} shortest-path {P_{xy}} in {G} . Since {\varphi} is {1} -Lipschitz, we conclude that it maps the whole path {P_{xy}} isometrically, thus {\|f(x)-f(y)\|_1=d_G(x,y)=d(x,y)} , showing that {\varphi|_{X}} is an isometry, and completing the proof. \Box