Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00227
Genus Distributions of Cubic Outerplanar Graphs
Jonathan L. Gross
Vol. 15, no. 2, pp. 295-316, 2011. Regular paper.
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.
Submitted: December 2009.
Reviewed: April 2011.
Revised: May 2011.
Reviewed: June 2011.
Revised: June 2011.
Accepted: July 2011.
Final: July 2011.
Published: July 2011.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX