Abstract
In this paper, we prove that 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\). Our results significantly improve and simplify the results of the recent paper by A. Sidiropoulos (Non-positive curvature and the planar embedding conjecture, FOCS (2013)).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alexander, R.: Planes for which the lines are the shortest paths between points. Ill. J. Math. 22, 177–190 (1978)
Bandelt, H.-J., Chepoi, V.: Metric graph theory and geometry: a survey. In: Goodman, J.E., Pach, J., Pollack, R. (eds.) Surveys on Discrete and Computational Geometry. Twenty Years Later. Contemporary Mathematics, vol. 453, pp. 49–86. AMS, Providence, RI (2008)
Baues, O., Peyerimhoff, N.: Curvature and geometry of tessellating plane graphs. Discrete Comput. Geom. 25, 141–159 (2001)
Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Isr. J. Math. 52, 46–52 (1985)
Bretagnolle, J., Dacunha Castelle, D., Krivine, J.-L.: Lois stables et espaces \(L_p\). Ann. Inst. Henri Poincaré, Nouv. Sér., Sect. B 2, 231–259 (1966)
Bridson, M.R., Haefliger, A.: Metric Spaces of Non-positive Curvature. Grundlehren Math. Wiss., vol. 319. Springer, Berlin (1999)
Chepoi, V., Dragan, F., Vaxès, Y.: Distance and routing problems in plane graphs of non-positive curvature. J. Algorithms 61, 1–30 (2006)
Chepoi, V., Fichet, B.: A note on circular decomposable metrics. Geom. Dedicata 69, 237–240 (1998)
Deza, M., Laurent, M.: Geometry of Cuts and Metrics. Algorithms Comb., vol. 15. Springer, Berlin (1997)
Dhandapani, R., Goodman, J.E., Holmsen, A., Pollack, R., Smorodinsky, S.: Convexity in topological affine planes. Discrete Comput. Geom. 38, 243–257 (2007)
Foertsch, T., Lytchak, A., Schroeder, V. : Non-positive curvature and the Ptolemy inequality. Int. Math. Res. Not. (2007). doi:10.1093/imrn/rnm100
Gromov, M.: Hyperbolic goups. In: Gersten, S.M. (ed.) Essays in Group Theory. MSRI Series, vol. 8. Springer, Berlin (1987)
Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and \(l_1\)-embeddings of graphs. Combinatorica 24, 233–269 (2004)
Indyk, P., Matoušek, J.: Low-distortion embeddings of finite metric spaces. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn, pp. 177–196. CRC Press LLC, Boca Raton (2004)
Maftuleac, D.: Algorithmique des complexes CAT(0) planaires et rectangulaires. Ph.D. thesis, Aix-Marseille Université. http://www.theses.fr/2012AIXM4032 (2012)
Matoušek, J.: Lectures on Discrete Geometry. Springer, New York (2002)
Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Comb. Theory, Ser. B 31, 75–81 (1981)
Papadopulos, A.: Metric Spaces, Convexity and Nonpositive Curvature, IRMA Lectures in Mathematics and Theoretical Physics, vol. 6. European Mathematical Society, Zurich (2005)
Sidiropoulos, A.: Non-positive curvature, and the planar embedding conjecture. FOCS 2013, pp. 177–186. http://arxiv.org/abs/1304.7512 (2013)
van de Vel, M.: Theory of Convex Structures. Elsevier, Amsterdam (1993)
Acknowledgments
The authors would like to thank James Lee for pointing out an error in the formulation of Theorem 2 in the first version of the article. They also thank the referee for careful reading and useful remarks.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chalopin, J., Chepoi, V. & Naves, G. Isometric Embedding of Busemann Surfaces into \(L_1\) . Discrete Comput Geom 53, 16–37 (2015). https://doi.org/10.1007/s00454-014-9643-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-014-9643-0