Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2010-003 (February 13, 2010)

Generating Internally Triconnected Rooted Graphs
by Bingbing Zhuang and Hiroshi Nagamochi

pdf File

A biconnected plane graph $G$ is called {\em internally triconnected} if any cut-pair consists of outer vertices and its removal results in only components each of which contains at least one outer vertex. In a rooted plane graph, an edge is designated as an outer edge with a specified direction. For given positive integers $n\geq 1$ and $g\geq 3$, let ${\cal G}_3(n,g)$ (resp., ${\cal G}_{\tt int}(n,g)$) denote the class of all triconnected (resp., internally triconnected) rooted plane graphs with exactly $n$ vertices such that the size of each inner face is at most $g$. In this paper, we present an efficient algorithm that enumerates all rooted plane graphs in ${\cal G}_{\tt int}(n,g)-{\cal G}_3(n,g)$ in $O(n)$ space and in $O(1)$-time delay.