Drawable and Forbidden Minimum Weight Triangulations

Lenhart, William J. and Liotta, Giuseppe (1998) Drawable and Forbidden Minimum Weight Triangulations. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 1-12(Official URL: http://dx.doi.org/10.1007/3-540-63938-1_45).

Full text not available from this repository.

Abstract

A graph is minimum weight drawable if it admits a straightline drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. In this paper we consider the problem of characterizing those graphs that are minimum weight drawable. Our contribution is twofold: We show that there exist infinitely many triangulations that are not minimum weight drawable. Furthermore, we present non-trivial classes of triangulations that are minimum weight drawable, along with corresponding linear time (real RAM) algorithms that take as input any graph from one of these classes and produce as output such a drawing. One consequence of our work is the construction of triangulations that are minimum weight drawable but none of which is Delaunay drawable-that is, drawable as a Delaunay triangulation.

Item Type:	Conference Paper
Additional Information:	10.1007/3-540-63938-1_45
Classifications:	P Styles > P.720 Straight-line G Algorithms and Complexity > G.999 Others G Algorithms and Complexity > G.140 Augmentation
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/68

Actions (login required)

View Item