# 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}$.

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

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$