Genus distributions of cubic series-parallel graphs
| Autoři | |
|---|---|
| Rok publikování | 2014 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Discrete Mathematics & Theoretical Computer Science |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/viewArticle/2146 |
| Obor | Informatika |
| Klíčová slova | graph embedding; genus distribution; series-parallel graphs; bounded treewidth |
| Popis | 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. |
| Související projekty: |