| Identifikační kód | RIV/00216224:14330/14:00080217 |
|---|
| Název v anglickém jazyce | Genus distributions of cubic series-parallel graphs |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2014 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 3 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Michal Kotrbčík (státní příslušnost: SK - Slovenská republika, domácí tvůrce: A)
Jonathan L. Gross (státní příslušnost: US - Spojené státy americké)
Timothy Sun (státní příslušnost: US - Spojené státy americké) |
|---|
| Popis výsledku v anglickém jazyce | 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 oftreewidth 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. |
|---|
| Klíčová slova oddělená středníkem | graph embedding; genus distribution; series-parallel graphs; bounded treewidth |
|---|
| Stránka www, na které se nachází výsledek | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/viewArticle/2146 |
|---|