Genus distributions of cubic series-parallel graphs
From MaRDI portal
Publication:2928586
zbMATH Open1301.05233arXiv1407.8031MaRDI QIDQ2928586FDOQ2928586
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)
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.
Full work available at URL: https://arxiv.org/abs/1407.8031
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
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)
