Genus distributions of cubic series-parallel graphs

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.129--146
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01188913
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 31 août 2015 - 17:03:51
Dernière modification le : jeudi 7 septembre 2017 - 01:03:47
Document(s) archivé(s) le : mardi 1 décembre 2015 - 10:44:46

Fichier

dmtcs-16-3-7.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01188913, version 1

Collections

Citation

Jonathan L. Gross, Michal Kotrbčík, Timothy Sun. Genus distributions of cubic series-parallel graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.129--146. 〈hal-01188913〉

Partager

Métriques

Consultations de la notice

29

Téléchargements de fichiers

83