Non-positive curvature

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.

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