Embeddings of cubic Halin graphs: Genus distributions

作者：Gross Jonathan L^*

来源：Ars Mathematica Contemporanea, 2013, 6(1): 37-56.

• genus distribution
• Halin graph
• partitioned genus distribution
• gram embedding
• outerplanar graph
• topological graph theory

We derive an O(n(2))-time algorithm for calculating the genus distribution of a 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.

• 出版日期2013