Genus Distributions of 4-Regular Outerplanar Graphs

Abstract

We present an $O(n^2)$-time algorithm for calculating the genus distribution of any 4-regular outerplanar graph. We characterize such graphs in terms of what we call split graphs and incidence trees. The algorithm uses post-order traversal of the incidence tree and productions that are adapted from a previous paper that analyzes double-root vertex-amalgamations and self-amalgamations.