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 , pp. 338-349(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_32).

Full text not available from this repository.

Abstract

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.

Item Type:	Conference Paper
Additional Information:	10.1007/3-540-44541-2_32
Classifications:	M Methods > M.999 Others Z Theory > Z.999 Others Z Theory > Z.250 Geometry
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/412

Actions (login required)

View Item