Genus distributions of cubic series-parallel graphs

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

KOTRBČÍK Michal GROSS Jonathan L. SUN Timothy

Rok publikování 2014
Druh Článek v odborném periodiku
Časopis / Zdroj Discrete Mathematics & Theoretical Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.