Drawable and Forbidden Minimum Weight Triangulations

Lenhart, William J. and Liotta, Giuseppe (1998) Drawable and Forbidden Minimum Weight Triangulations. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 1-12 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_45).

Full text not available from this repository.

Abstract

A graph is minimum weight drawable if it admits a straightline drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. In this paper we consider the problem of characterizing those graphs that are minimum weight drawable. Our contribution is twofold: We show that there exist infinitely many triangulations that are not minimum weight drawable. Furthermore, we present non-trivial classes of triangulations that are minimum weight drawable, along with corresponding linear time (real RAM) algorithms that take as input any graph from one of these classes and produce as output such a drawing. One consequence of our work is the construction of triangulations that are minimum weight drawable but none of which is Delaunay drawable-that is, drawable as a Delaunay triangulation.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_45
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.140 Augmentation
ID Code:68

Repository Staff Only: item control page

References

O. Aichholzer, F. Aurenhammer, S.-W. Cheng, N. Katoh, M. Taschwer, G. Rote, and Y.-F. Xu. Triangulations intersect nicely. Discrete Comput. Geom., 16:339-359, 1996.

P. Bose, G. Di Battista, W. Lenhart, and G. Liotta. Proximity constraints and representable trees. In R. Tamassia and I.G. Tollis, editors, Graph Drawing (Proc. GD '94) volume 894 of Lecture Notes Comput. Sci., pages 340-351. Springer-Verlag, 1995.

P. Bose, W. Lenhart, and G. Liotta. Characterizing proximity trees. Algorithmica, 16:83-110, 1996. (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

S.-W. Cheng and Y.-F. Xu. Approaching the largest \beta-skeleton within a minimum weight triangulation. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 196-203, 1996.

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 Comput. Sci., pages 328-339. Springer-Verlag, 1995.

G. Di Battista, G. Liotta, and S. H. Whitesides. The strength of weak proximity. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD '95) volume 1027 of Lecture Notes Comput. Sci., pages 178-189. Springer-Verlag, 1996.

G. Di Battista and L. Vismara. Angles of planar triangular graphs. SIAM J. Discrete Math., 9(3):349-359, 1996.

M. T. Dickerson, S. A. McElfresh, and M. H. Montague. New algorithms and empirical findings on minimum weight triangulation heuristics. In Proc. 11th Annu. ACM Sympos. Comput. Geom. pages 238-247, 1995.

M. T. Dickerson and M. H. Montague. A (usually?) connected subgraph of the minimum weight triangulation. In Proc. 12th Annu. ACM Sympos. Comput. Geom. pages 204-213, 1996.

M. B. Dillencourt. Realizability of Delaunay triangulations. Inform. Process. Lett., 33:283-287, 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).

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979.

M. Keil. Computing a subgraph of the minimum weight triangulation. Comput. Geom. Theory Appl., 4:13-26, 1994.

D. G. Kirkpatrick. Anote on Delaunay and optimal triangulations. Inform. Process. Lett., 10:127-128, 1980.

W. Lenhart and G. Liotta. Drawing outerplanar minimum weight triangulations. Inform. Process. Lett., 6(12):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 Comput. Sci., pages 373-384. Springer-Verlag, 1996.

W. Lenhart and G. Liotta. Proximity drawings of outerplanar graphs. In S. North, editor,Graph Drawing (Proc. GD '96) volume 1190 of Lecture Notes Comput. Sci., pages 286-302. Springer-Verlag, 1997.

C. Levcopoulos and D. Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. In Proc. 7th ACM-SIAM Sympos. Discrete Algorithms, pages 392-401, 1996.

C. Levcopoulos and D. Krznaric. Tight lower bounds for minimum weight triangulation heuristics. Information Processing Letters, (57):129-135, 1996.

A. Lingas. A new heuristic for minimum weight triangulation. SIAM J. Algebraic Discrete Methods, 8(4):646-658, 1987.

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

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

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

H. Meijer and D. Rappaport. Computing the minimum weight triangulation of a set of linearly ordered points. Imformation Processing Letters, (42):35-38, 1992.

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