Minimum Weight Drawings of Maximal Triangulations

This paper studies the drawability problem for minimum weight triangulations, i.e. whether a triangulation can be drawn so that the resulting drawing is the minimum weight triangulations of the set of its vertices. We present a new approach to this problem that is based on an application of a well known matching theorem for geometric triangulations. By exploiting this approach we characterize new classes of minimum weight drawable triangulations in terms of their skeletons. The skeleton of a minimum weight triangulation is the subgraph induced by all vertices that do not belong to the external face. We show that all maximal triangulations whose skeleton is acyclic are minimum weight drawable, we present a recursive method for constructing infinitely many minimum weight drawable triangulations, and we prove that all maximal triangulations whose skeleton is a maximal outerplanar graph are minimum weight drawable.