How to Draw Outerplanar Minimum Weight TriangulationsLenhart, 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.
Official URL: http://dx.doi.org/10.1007/BFb0021821
AbstractIn 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.
Actions (login required)
|