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 Outerplanar 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 algorithm, graph algorithm, planar graph, outerplanar graph, symmetry,
Full Text: PDF>>
In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers n ≥ 3 and g ≥ 3, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly n vertices such that the size of each inner face is at most g without delivering two symmetric copies of the same graph.