Voronoi Drawings of Trees

Liotta, Giuseppe and Meijer, Henk (1999) Voronoi Drawings of Trees. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 369-378 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_38).

Full text not available from this repository.

Abstract

This paper investigates the following problem: Given a tree T, can we find a set of points in the plane such that the Voronoi diagram of this set of points is a drawing of T? We study trees that can be drawn as Voronoi diagrams both in the Euclidean and in the Manhattan metric. Characterizations of drawable trees are given and different drawing algorithms that take into account additional geometric constraints are presented.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_38
Classifications:M Methods > M.999 Others
M Methods > M.900 Tree
P Styles > P.999 Others
ID Code:383

Repository Staff Only: item control page

References

F. Aurenhammer. Voronoi diagrams: A survey of a fundamental geometric data structure. ACM Comput. Surv., 23(3):345-405, Sept. 1991.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

G. Di Battista, W. Lenhart, and G. Liotta. Proximity drawability: a survey. In R. Tamassia and I. G. Tollis, editors, Graph Drawing (Proc. GD '94), volume 894 of Lecture Notes in Comput. Sci., pages 328-339. Springer-Verlag, 1995.

M. B. Dillencourt. Realizability of Delaunay triangulations. Inform. Process. Lett., 33(6):283-287, Feb. 1990.

M. B. Dillencourt. Toughness and Delaunay triangulations. Discrete Comput. Geom., 5:575-601, 1990

M. B. Dillencourt and W. D. Smith. Graph-theoretical conditions for inscribability and Delaunay realizability. In Proc. 6th Canad. Conf. Comput. Geom., pages 287-292, 1994.

P. Eades and S. Whitesides. The realization problem for Euclidean minimum spanning trees is NP-hard. Algorithmica, 16:60-82, 1996. (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

G. Liotta and G. Di Battista. Computing proximity drawings of trees in the 3-dimensional space. In Proc. 4th Workshop Algorithms and Data Struct., volume 955 of Lecture Notes Comput. Sci., pages 239-250. Springer-Verlag, 1995.

G. Liotta, A. Lubiw, H. Meijer, and S. H. Whitesides. The rectangle of influence drawability problem. Comput. Geom. Theory and Appl., 10(1):1-22, 1998.

G. Liotta, R. Tamassia, I. G. Tollis, and P. Vocca. Area requirement of Gabriel drawings. In Algorithms and Complexity (Proc. CIAC' 97), volume 1203 of Lecture Notes Comput. Sci., pages 135-146, Springer-Verlag, 1997.

C. Monma and S. Suri. Transitions in geometric minimum spanning trees. Discrete Comput. Geom., 8:265-293, 1992.

A. Okabe, B. Boots, and K. Sugihara. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Chichester, UK, 1992.

F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 3rd edition, 1988.

K. Sugihara and M. Iri. Construction of the Voronoi diagram for 'one million" generators in single-precision arithmetic. Proc. IEEE, 80(9):1471-1484, Sept. 1992.