Genus Distributions of cubic series-parallel graphs

2014/07/30 by Gross, Jonathan L., Kotrbčík, Michal, Sun, Timothy · 1 citation
#05C10 #05C30 #05C85 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.1407.8031

Abstract

We derive a quadratic-time algorithm for the genus distribution of any 3-regular, biconnected series-parallel graph, which we extend to any biconnected series-parallel graph of maximum degree at most 3. Since the biconnected components of every graph of treewidth 2 are series-parallel graphs, this yields, by use of bar-amalgamation, a quadratic-time algorithm for every graph of treewidth at most 2 and maximum degree at most 3.

Cited by

• On the Genus Polynomial of Cubic Graphs

Related

• Euler-genus distributions of cubic Halin graphs
• The genus distribution of cubic graphs and asymptotic number of rooted cubic maps with high genus
• Log-Concavity of Combinations of Sequences and Applications to Genus Distributions
• A Practical Algorithm for the Computation of the Genus
• Genus distribution polynomials for bicellular bicolored maps all with real zeros