Embeddings of cubic Halin graphs: Genus distributions

Jonathan L. Gross


We derive an O(n2)-time algorithm for calculating the genus distribution of a given 3-regular Halin graph G; that is, we calculate the sequence of numbers g0(G), g1(G), g2(G), … on the respective orientable surfaces S0, S1, S2, …. 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.


Genus distribution, Halin graph, partitioned genus distribution, gram embedding, outerplanar graph, topological graph theory.

Full Text:


DOI: https://doi.org/10.26493/1855-3974.217.440

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications