For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs
Bingbing ZHUANG Hiroshi NAGAMOCHI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2011/02/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
enumeration, reflective symmetry, triangulation, plane graphs, planar graphs, biconnectivity, graph algorithms,
Full Text: PDF(886.5KB)>>
In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.