Minimum Weight Drawings of Maximal Triangulations (Extended Abstract)

Lenhart, William J. and Liotta, Giuseppe (2001) Minimum Weight Drawings of Maximal Triangulations (Extended Abstract). In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 338-349 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_32).

Full text not available from this repository.

Abstract

This paper studies the drawability problem for minimum weight triangulations, i.e. whether a triangulation can be drawn so that the resulting drawing is the minimum weight triangulations of the set of its vertices. We present a new approach to this problem that is based on an application of a well known matching theorem for geometric triangulations. By exploiting this approach we characterize new classes of minimum weight drawable triangulations in terms of their skeletons. The skeleton of a minimum weight triangulation is the subgraph induced by all vertices that do not belong to the external face. We show that all maximal triangulations whose skeleton is acyclic are minimum weight drawable, we present a recursive method for constructing infinitely many minimum weight drawable triangulations, and we prove that all maximal triangulations whose skeleton is a maximal outerplanar graph are minimum weight drawable.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_32
Classifications:M Methods > M.999 Others
Z Theory > Z.999 Others
Z Theory > Z.250 Geometry
ID Code:412

Repository Staff Only: item control page

References

Oswin Aichholzer, Franz Aurenhammer, Siu-Wing Chen, Na oki Katoh, Michael Tachwer, Günter Rote, and Yin-Feng Xu. Triangulations intersect nicely. Discrete Comput. Geom., 16:339-359, 1996.

T. Biedl, A. Bretscher, and H. Meijer. Drawings of graphs without filled 3-cycles. In Graph Drawing (Proc. GD '99), volume 1731 of Lecture Notes Comput. Sci., pages 359-368, 2000.

J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Macmillan, London, 1976.

P. Bose, W. Lenhard, and G. Liotta. Characterizing proximity trees. Algorithmica, 16:83-110, 1996.

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), volume894 of Lecture Notes in Computer Science, pages 328-339, 1995.

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

M. B. Dillencourt. Thoughness and Delaunay triangulations. Discrete Comput. Geom., 5, 1990.

M. B. Dillencourt and W. D. Smith. Graph-theoretical conditions for inscribability and Delaunayr ealizability. 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.

W. Lenhart and G. Liotta. Drawing outerplanar minimum weight triangulations. Inform. Process. Lett., 57(5):253-260, 1996.

W. Lenhart and G. Liotta. How to draw outerplanar minimum weight triangulations. In F. J. Brandenburg, editor, Graph DRawing (Proc. GD '95), volume 1027 of Lecture Notes in Computer Science, pages 373-384. Springer-Verlag, 1996.

William Lenhart and Giuseppe Liotta. Drawable and forbidden minimum weight triangulations. In G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes in Computer Science, pages 1-12. Springer-Verlag, 1998.

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

G. Liotta and H. Meijer. Voronoi drawings of trees. In Graph Drawing (Proc. GD '99), volume 894 of Lecture Notes in Computer Science, pages 328-339, 2000.

A. Lubiw and N. Sleumer. Maximal outerplanar graphs are relative neighborhood graphs. In Proc. 5th Canad. Conf. Comput. Geom., pages 198-203, 1993.

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

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

Cao An Wang, Francis Y. Chin, and Boting Yang. Maximum weight triangulation and graph drawing. Inform. Process. Lett., 70(1):17-22, 1999.

Cao An Wang, Francis Y. Chin, and Boting Yang. Triangulations without minimum weight drawing. In Algorithms and Complexity (Proc. CIAC 2000), volume 1767 of Lecture Notes Comput. Sci., pages 163-173. Springer-Verlag, 2000.