
For FullText 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
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E94D
No.2
pp.211219 Publication Date: 2011/02/01 Online ISSN: 17451361
DOI: 10.1587/transinf.E94.D.211 Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science  Mathematical Foundations and Applications of Algorithms and Computer Science ) Category: Keyword: enumeration algorithm, graph algorithm, planar graph, outerplanar graph, symmetry,
Full Text: PDF>>
Summary:
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.

