Genus Distributions of Cubic Outerplanar Graphs

Abstract

We present a quadratic-time algorithm for computing the genus distribution of any 3-regular outerplanar graph. Although recursions and some formulas for genus distributions have previously been calculated for bouquets and for various kinds of ladders and other special families of graphs, cubic outerplanar graphs now emerge as the most general family of graphs whose genus distributions are known to be computable in polynomial time. The key algorithmic features are the syntheses of the given outerplanar graph by a sequence of edge-amalgamations of some of its subgraphs, in the order corresponding to the post-order traversal of a plane tree that we call the inner tree, and the coordination of that synthesis with just-in-time root-splitting.