Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane

Sarkar , Rik (2012) Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 355-366 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_34).

Full text not available from this repository.


This paper considers the problem of embedding trees into the hyperbolic plane. We show that any tree can be realized as the Delaunay graph of its embedded vertices. Particularly, a weighted tree can be embedded such that the weight on each edge is realized as the hyperbolic distance between its embedded vertices. Thus the embedding preserves the metric information of the tree along with its topology. The distance distortion between non adjacent vertices can be made arbitrarily small – less than a (1 + ε) factor for any given ε. Existing results on low distortion of embedding discrete metrics into trees carry over to hyperbolic metric through this result. The Delaunay character implies useful properties such as guaranteed greedy routing and realization as minimum spanning trees.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_34
Classifications:G Algorithms and Complexity > G.490 Embeddings
M Methods > M.900 Tree
P Styles > P.420 Hyper
ID Code:1269

Repository Staff Only: item control page


Chepoi, V., Dragan, F., Estellon, B., Habib, M., Vaxès, Y., Xiang, Y.: Additive spanners and distance and routing labeling schemes for hyperbolic graphs. Algorithmica, 1–20 (2010), doi:10.1007/s00453-010-9478-x

Cvetkovski, A., Crovella, M.: Hyperbolic embedding and routing for dynamic graphs. In: Proceedings of Infocom 2009 (April 2009)

Dhamdhere, K., Gupta, A., Räke, H.: Improved embeddings of graph metrics into random trees. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006, pp. 61–69 (2006)

Elkin, M., Emek, Y., Spielman, D.A., Teng, S.-H.: Lower-stretch spanning trees. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 494–503 (2005)

Eppstein, D., Goodrich, M.T.: Succinct Greedy Graph Drawing in the Hyperbolic Plane. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 14–25. Springer, Heidelberg (2009)

Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, pp. 448–455 (2003)

Greenberg, M.J.: Euclidean and Non-Euclidean Geometries. W.H. Freeman (1993)

Gromov, M.: Hyperbolic groups. In: Essays In Group Theory, pp. 75–263. Springer, New York (1987)

Kleinberg, R.: Geographic routing using hyperbolic space. In: Proceedings of the 26th Conference of the IEEE Communications Society (INFOCOM 2007), pp. 1902–1909 (2007)

Lee, J., Naor, A., Peres, Y.: Trees and markov convexity. Geometric and Functional Analysis 18, 1609–1659 (2009), doi:10.1007/s00039-008-0689-0

Monma, C., Suri, S.: Transitions in geometric minimum spanning trees (extended abstract). In: Proceedings of the Seventh Annual Symposium on Computational Geometry, pp. 239–249 (1991)

Papadopoulos, F., Krioukov, D., Boguñá, M., Vahdat, A.: Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In: Proceedings of the 29th Conference on Information Communications, INFOCOM 2010, pp. 2973–2981 (2010)

Sarkar, R.: Low distortion delaunay embedding of trees in hyperbolic plane, http://page.inf.fu-berlin.de/sarkar/papers/HyperbolicDelaunayFull.pdf

Tanuma, T., Imai, H., Moriyama, S.: Revisiting hyperbolic voronoi diagrams from theoretical, applied and generalized viewpoints. In: International Symposium on Voronoi Diagrams in Science and Engineering, pp. 23–32 (2010)

Zeng, W., Sarkar, R., Luo, F., Gu, X.D., Gao, J.: Resilient routing for sensor networks using hyperbolic embedding of universal covering space. In: Proc. of the 29th Annual IEEE Conference on Computer Communications (INFOCOM 2010) (April 2010)