Genus distributions of cubic series-parallel graphs
| Authors | |
|---|---|
| Year of publication | 2014 |
| Type | Article in Periodical |
| Magazine / Source | Discrete Mathematics & Theoretical Computer Science |
| MU Faculty or unit | |
| Citation | |
| Web | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/viewArticle/2146 |
| Field | Informatics |
| Keywords | graph embedding; genus distribution; series-parallel graphs; bounded treewidth |
| Description | 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. |
| Related projects: |