Genus distributions of 4-regular outerplanar graphs (Q648404)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Genus distributions of 4-regular outerplanar graphs |
scientific article; zbMATH DE number 5976490
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Genus distributions of 4-regular outerplanar graphs |
scientific article; zbMATH DE number 5976490 |
Statements
Genus distributions of 4-regular outerplanar graphs (English)
0 references
22 November 2011
0 references
Summary: We present an \(O(n^2)\)-time algorithm for calculating the genus distribution of any 4-regular outerplanar graph. We characterize such graphs in terms of what we call split graphs and incidence trees. The algorithm uses post-order traversal of the incidence tree and productions that are adapted from a previous paper that analyzes double-root vertex-amalgamations and self-amalgamations.
0 references
split graphs
0 references
incidence trees
0 references
0.8098762035369873
0 references
0.8082950711250305
0 references
0.8023446798324585
0 references
0.7868433594703674
0 references
0.7832083702087402
0 references
