DRAWING OUTERPLANAR MINIMUM WEIGHT TRIANGULATIONS

We consider the problem of characterizing those graphs that can be dra wn as minimum weight triangulations and answer the question for maxima l outerplanar graphs. We provide a complete characterization of minimu m weight triangulations of regular polygons by studying the combinator ial 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 dra wing of G that is a minimum weight triangulation of the set of points representing the vertices of G.