Genus Distributions of 4-Regular Outerplanar Graphs
Mehvish I. Poshni, Imran F. Khan, Jonathan L. Gross · The Electronic Journal of Combinatorics · 2011
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.