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