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
Theorem 1 Suppose 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 2 Every 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.