The search functionality is under construction.
The search functionality is under construction.

Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs

Bingbing ZHUANG, Hiroshi NAGAMOCHI

  • Full Text Views

    0

  • Cite this

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.

Publication
IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.211-219
Publication Date
2011/02/01
Publicized
Online ISSN
1745-1361
DOI
10.1587/transinf.E94.D.211
Type of Manuscript
Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
Category

Authors

Keyword