Isometric embedding of Busemann surfaces into \(L_1\) (Q2256580): Difference between revisions

Bilipschitz embeddability (with uniformly bounded distortions) of planar graphs with their graph distances into \(L_1\) is one of the well-known conjectures in the theory of metric embeddings. Recently \textit{A. Sidiropoulos} [Non-positive curvature and the planar embedding conjecture. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science-FOCS 2013, 177--186, IEEE Computer Soc., Los Alamitos, CA, (2013)] contributed to this study by proving the following result: There exists a universal constant \(\gamma > 1\) such that every shortest-path metric of a planar graph which can be realized as a set of points in a surface of non-positive curvature admits an embedding into \(L_1\) with distortion at most \(\gamma\). The proof of Sidiropoulos is combinatorial and probabilistic. The present authors prove the following strengthening of the result of Sidiropoulos. From the abstract: ``Any non-positively curved \(2\)-dimensional surface (alias, Busemann surface) is isometrically embeddable into \(L_1\). As a corollary, we obtain that all planar graphs which are \(1\)-skeletons of planar non-positively curved complexes with regular Euclidean polygons as cells are \(L_1\)-embeddable with distortion at most \(2\).'' The proof in this paper is geometric and is based on a Crofton formula proved by the authors for finite subsets in general position of Busemann surfaces, which generalizes an analogous result of \textit{R. Alexander} [Ill. J. Math. 22, 177--190 (1978; Zbl 0379.50002)].