How to Draw Outerplanar Minimum Weight Triangulations

Lenhart, William and Liotta, Giuseppe (1996) How to Draw Outerplanar Minimum Weight Triangulations. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 373-384 (Official URL: http://dx.doi.org/10.1007/BFb0021821).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021821
Classifications:Z Theory > Z.999 Others
P Styles > P.720 Straight-line
G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
ID Code:180

Repository Staff Only: item control page

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. Algorithm 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 \Omega(\sqrt{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.