How to Draw Outerplanar Minimum Weight Triangulations

Lenhart, William J. and Liotta, Giuseppe (1996) How to Draw Outerplanar Minimum Weight Triangulations. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995 , 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
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/180

Actions (login required)

View Item