Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationGraph Drawing
Subtitle of host publication19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers
PublisherSpringer Berlin Heidelberg
Pages355-366
Number of pages12
Volume7034
ISBN (Electronic)978-3-642-25878-7
ISBN (Print)978-3-642-25877-0
DOIs
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane'. Together they form a unique fingerprint.

Cite this