Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2010-001 (January 13, 2010)

Enumerating Biconnected Rooted Plane Graphs
by Bingbing Zhuang and Hiroshi Nagamochi

pdf File


A plane graph is a drawing of a planar graph in the plane such that no two edges cross each other. A rooted plane graph has a designated outer vertex. For given positive integers $n$ and $g$, let ${\cal G}(n,g)$ denote the set of all biconnected rooted plane graphs with exactly $n$ vertices such that the size of each inner face is at most $g$. In this paper, we give an algorithm that enumerates all plane graphs in ${\cal G}(n,g)$. The algorithm runs in constant time per each by outputting the difference from the previous output.