**Isometric embedding of non-positively curved surfaces into **

As I have mentioned before, one of my favorite questions is whether the shortest-path metric on a planar graph embeds into with distortion. This is equivalent to such graphs having an -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 .

In a paper of Tasos Sidiropoulos, it is proved that every simply-connected surface of *non-positive curvature* admits a bi-Lipschitz embedding into . A followup work of Chalopin, Chepoi, and Naves shows that actually such a surface admits an *isometric* emedding into . 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 is a geodesic metric space (i.e. the distance between any pair of points is realized by a geodesic whose length is ). One says that has *non-positive curvature* (in the sense of Busemann) if for any pair of geodesics and , the map given by

is convex.

Theorem 1Suppose that is homeomorphic to and is endowed with a geodesic metric such that has non-positive curvature. Then embeds isometrically in .

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

Lemma 2Every geodesic in 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 . Let denote the convex hull of . (A set is *convex* if for every we have for every geodesic connecting to .)

It is an exercise to show that the boundary of is composed of a finite number of geodesics between points . For every pair , let denote a geodesic line containing and which exists by Lemma 2. Consider the collection of sets , and let denote the set of intersection points between geodesics in . Since is a collection of geodesics, and all geodesics intersect at most once (an easy consequence of non-positive curvature), the set is finite.

Consider finally the set . The geodesics in naturally endow with the structure of a planar graph , where two vertices are adjacent if they lie on a subset of some geodesic in and the portion between and does not contain any other points of . Note that is the outer face of in the natural drawing, where is the boundary of (the union of the geodesics in ).

We can put a path metric on this graph by defining the length of an edge as . Let denote the induced shortest-path metric on the resulting graph. By construction, we have the following two properties.

- If or for some , then .
- For every , there is a shortest path between two vertices in such that .

Both properties follow from our construction using the lines .

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

Theorem 3 (Okamura-Seymour dual version)For every planar graph and face , there is a -Lispchitz mapping such that is an isometry.

Let us apply this theorem to our graph and face . Consider and . By property (1) above, we have . Since , from Theorem 3, we have . But property (2) above says that and lie on a – shortest-path in . Since is -Lipschitz, we conclude that it maps the whole path isometrically, thus , showing that is an isometry, and completing the proof.