Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs

Bingbing ZHUANG  Hiroshi NAGAMOCHI  

IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.2   pp.211-219
Publication Date: 2011/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.211
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(722.6KB)>>
Buy this Article

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.