Generating Internally Triconnected Rooted Plane Graphs
A biconnected plane graph G is called 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≥1 and g≥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 O(1)-time delay algorithm that enumerates all rooted plane graphs in ${\cal G}_{\tt int}(n,g)-{\cal G}_3(n,g)$ in O(n) space.