![Důležité termíny](https://cdn.muni.cz/media/3633704/image_2.jpg?mode=crop¢er=0.5,0.5&rnd=133572412150000000&heightratio=0.5&width=278)
Informace o publikaci
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: |