Embeddings of cubic Halin graphs: Genus distributions - Gross, Jonathan L. (Ars mathematica contemporanea, 2013)
We derive an ?$O(n^2)$?-time algorithm for calculating the genus distribution ofa given 3-regular Halin graph $G$; that is, we calculate the sequence of numbers ?$g_0(G$)?, ?$g_1(G)$?, ?$g_2(G), …$? on the respective orientable surfaces ?$S_0$?, ?$S_1$?, ?$S_2, … \;$?. Key topological features are a quadrangular decomposition of plane Halin graphs and a new recombinant-strands reassembly process that fits pieces together three-at-a-vertex. Key algorithmic features are reassembly along a post-order traversal, with just-in-time dynamic assignment of roots for quadrangular pieces encountered along the tour.
Keywords: genus distribution; gram embedding; Halin graph; outerplanar graph; partitioned genus distribution; topological graph theory