Abstract
In this paper we consider the problem of characterizing those graphs that can be drawn as minimum weight triangulations and answer the question for maximal outerplanar graphs. We provide a complete characterization of minimum weight triangulations of regular polygons by studying the combinatorial properties of their dual trees. We exploit this characterization to devise a linear time (real RAM) algorithm that receives as input a maximal outerplanar graph G and produces as output a straight-line drawing of G that is a minimum weight triangulation of the set of points representing the vertices of G.
Research supported in part by the National Science Foundation under grant CCR-9423847, by the U.S. Army Research Office under grant 34990-MA-MUR, by Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the Italian National Research Council (CNR), and by N.A.T.O.- CNR Advanced Fellowships Programme.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
O. Aichholzer, F. Aurenhammer, G. Rote, M. Taschwer. Triangulations Intersect Nicely. Proceedings 11th ACM Symposium on Computational Geometry, Vancouver, Canada, 1995, pp. 220–229.
J.A. Bondy and U.S.R. Murty. Graph Theory with Applications. Elsevier Science, New York, 1976.
G. Di Battista, P. Eades, R. Tamassia and I.G. Tollis. Algorithms for Automatic Graph Drawing: An Annotated Bibliography. Computational Geometry: Theory and Applications, 4, 1994, pp. 235–282.
M.T. Dickerson, S.A. McElfresh, M. Montague. New Algorithms and Empirical Findings on Minimum Weight Triangulations Heuristics. Proceedings 11th ACM Symposium on Computational Geometry, Vancouver, Canada, 1995, pp. 238–247.
P. Eades and S. Whitesides. The Realization Problem for Euclidean Minimum Spanning Tree is NP-hard. Proceedings 10th ACM Symposium on Computational Geometry, Stony Brook NY, USA, 1994, pp. 49–56.
M.R. Garey and D.S. Johnson. Computers and Intractability-A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.
P.N. Gilbert. New Results in Planar Triangulations. M.Sc. Thesis, Coordinated Science Laboratory, University of Illinois, Urbana, IL, 1979.
L.S. Heath and S.V. Pemmaraju. New Results for the Minimum Weight Triangulation Problem. Algorithmica, 12, 1994 pp. 533–552.
J.M. Keil. Computing a Subgraph of the Minimum Weight Triangulation. Computational Geometry: Theory and Applications, 4, 1994, pp. 13–26.
D. G. Kirkpatrick. A Note on Delaunay and Optimal Triangulations, information Processing Letters, 10, 1980, pp. 127–128.
G.T. Klincsek. Minimal triangulations of Polygonal Domains. Ann. Discrete Math., 9, 1980, pp. 121–123.
C. Levcopoulos. An Ω(√n) Lower Bound for the Nonoptimality of the Greedy Triangulation. Information Processing Letters, 25, 1987, pp. 247–251.
C. Levcopoulos and A. Lingas. On Approximation Behavior of the Greedy Triangulation for Convex Polygons. Algorithmica, 2, 1987, pp. 175–193.
A. Lingas. A Linear-Time Heuristic for Minimum Weight Triangulation of Convex Polygons. Proc. 23rd Allerton Conference on Computing, Communication, and Control, Urbana, 1985, pp. 480–485.
A. Lingas. The Greedy and Delaunay Triangulations are not Bad in the Average Case. Information Processing Letters, 22, 1986, pp. 25–31.
A. Lingas. A New Heuristic for Minimum Weight Triangulation. SIAM J. Algebraic Discrete Methods, 8, 1987, pp. 646–658.
E.L. Lloyd. On Triangulations of a Set of Points in the Plane. Proceedings of the 18th Conference on the Foundations of Computer Science, Providence, RI, 1977, pp. 228–240.
K. Manacher, L. Zobrist. Neither the Greedy nor the Delaunay Triangulation of a Planar Point Set Approximates the Optimal Triangulation. Information Processing Letters, 9, 1979, pp. 31–34.
H. Meijer and D. Rappaport. Computing the Minimum Weight Triangulation of a Set of Linearly Ordered Points. Information Processing Letters, 42, 1992, pp. 35–38.
C. Monma and S. Suri. Transitions in Geometric Minimum Spanning Trees. Proc. 7th ACM Symposium on Computational Geometry, 1991, pp. 239–249.
F. P. Preparata and M. I. Shamos, Computational Geometry — an Introduction. Springer-Verlag, New York, 1985.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lenhart, W., Liotta, G. (1996). How to draw outerplanar minimum weight triangulations. In: Brandenburg, F.J. (eds) Graph Drawing. GD 1995. Lecture Notes in Computer Science, vol 1027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0021821
Download citation
DOI: https://doi.org/10.1007/BFb0021821
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60723-6
Online ISBN: 978-3-540-49351-8
eBook Packages: Springer Book Archive