Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
DOI: 10.7155/jgaa.00234
Generating All Triangulations of Plane Graphs
Vol. 15, no. 3, pp. 457482, 2011. Regular paper.
Abstract In this paper, we deal with the problem of generating all triangulations of plane graphs.
We give an algorithm for generating all triangulations of a triconnected 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 G in O(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 triconnected plane graph; although there exist algorithms for generating triangulated graphs with certain properties.
Our algorithm for generating all triangulations of a triconnected plane graph needs to find all triangulations of
each face (a cycle) of the graph.
We give an algorithm to generate all triangulations of a cycle C of n vertices in time O(1) per triangulation, where the vertices of C are numbered.
Finally, we give an algorithm for generating all triangulations of a cycle C of n vertices in time O(n^{2}) per triangulation, where vertices of C are not numbered.
Key words: Triangulation; Graph; Cycle; Plane Graph; Genealogical Tree.

Submitted: May 2009.
Reviewed: October 2009.
Revised: July 2010.
Accepted: October 2010.
Final: November 2010.
Published: July 2011.
