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.
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.
Repository Staff Only: item control page