Abstract:
Generating all triangulations of graphs and polygons have many applications in Computational
Geometry, VLSI Floorplaning and Graph Drawing. In this thesis, we deal
with the problem of generating all triangulations of plane graphs. We give an algorithm
for generating all triangulations of a biconnected plane graph G of n vertices. Our algorithm
establishes a tree structure among the triangulations of G, called the "tree of
triangulations," and generates each triangulation of Gin 0(1) time. The algorithm uses
O(n) space and generates all triangulations of G without duplications. To the best of
our knowledge, our algorithm is the first algorithm for generating all triangulations of
a biconnected plane graph; although there exist algorithms for generating triangulated
graphs with certain properties. Our algorithm for generating all triangulations of a plane
graph needs to find all triangulations of a convex polygon. 'vVegive an algorithm to generate
all triangulations of a convex polygon P of n vertices in time 0(1) per triangulation,
where the vertices of P are numbered. Our algorithm for generating all triangulations of
a convex polygon also improves previous results; existing algorithms need to generate all
triangulations of convex polygons of less than n vertices before generating the triangulations
of a convex polygon of n vertices. Finally, we give an algorithm for generating all
triangulations of a convex polygon P of n vertices in time 0(n2
) per triangulation, where
vertices of P are not numbered.
