Genus distributions of cubic series-parallel graphs

MaRDI QIDQ2928586zbMATH OpenFDO

Authors Jonathan L. Gross, Michal Kotrbčík, Timothy Sun

Publication date 10 November 2014

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.8031, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2146/0.html

zbMATH Keywords

bounded treewidthgraph embeddingseries-parallel graphsgenus distribution

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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.

Recommendations

• Embeddings of cubic Halin graphs: genus distributions
• Genus distributions of 4-regular outerplanar graphs
• Euler-genus distributions of cubic caterpillar-Halin graphs
• Embeddings of graphs of fixed treewidth and bounded degree
• Genus distribution for a graph

Cited in

(9)

• Genus distributions for iterated claws
• The genus distribution of cubic graphs and asymptotic number of rooted cubic maps with high genus
• Genus distributions of 4-regular outerplanar graphs
• Genus distribution for a graph
• Recursive formulas for embedding distributions of cubic outerplanar graphs
• Euler-genus distributions of cubic caterpillar-Halin graphs
• Embeddings of cubic Halin graphs: genus distributions
• Embeddings of graphs of fixed treewidth and bounded degree
• Enumerating graph embeddings and partial-duals by genus and Euler genus

This page was built for publication: Genus distributions of cubic series-parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2928586)