Minimum Weight Drawings of Maximal Triangulations (Extended Abstract)
Lenhart, William J. and Liotta, Giuseppe (2001) Minimum Weight Drawings of Maximal Triangulations (Extended Abstract). In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 338-349 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_32).
Full text not available from this repository.
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.
Repository Staff Only: item control page