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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1269

Actions (login required)

View Item View Item