Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2010-002 (February 11, 2010)

Listing Triconnected 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\geq 1$ and $g\geq 3$, let ${\cal G}_3(n,g)$ denote the set of all triconnected 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}_3(n,g)$. The algorithm runs in constant time per each by outputting the difference from the previous output.