Genus Distributions of 4-Regular Outerplanar Graphs

Mehvish I. Poshni, Imran F. Khan, Jonathan L. Gross


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.

Full Text: PDF