Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2010-008 (April 02, 2010)

Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs
by Bingbing Zhuang and Hiroshi Nagamochi

pdf File

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\geq 3$ and $g\geq 3$, we give an $O(n)$-space and $O(1)$-time delay algorithm that enumerates 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.