Drawing Outerplanar Minimum Weight Triangulations (short abstract)

this paper we examine the problem of characterizing those triangulations admitting a minimum weight drawing and answer the question for maximal outerplanar graphs. The contribution is twofold: 1. Minimum weight triangulations for points that are vertices of a regular polygons are characterized. The characterization is based on the combinatorial structure of the dual tree of the minimum weight triangulations of such point sets. A consequence of the characterization is an optimal time algorithm for computing a minimum weight triangulation of a regula