Generating All Triangulations of Plane Graphs
Vol. 15, no. 3, pp. 457-482, 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(n2) 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.
Communicated by Sandip Das and Ryuhei Uehara
article (PDF)