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
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.