On the Book Thickness of k-Trees

Abstract : Every k-tree has book thickness at most k + 1, and this bound is best possible for all k \textgreater= 3. Vandenbussche et al. [SIAM J. Discrete Math., 2009] proved that every k-tree that has a smooth degree-3 tree decomposition with width k has book thickness at most k. We prove this result is best possible for k \textgreater= 4, by constructing a k-tree with book thickness k + 1 that has a smooth degree-4 tree decomposition with width k. This solves an open problem of Vandenbussche et al.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.39--44
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990475
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:38:57
Dernière modification le : mardi 6 février 2018 - 14:48:02
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:17:23

Fichier

1778-6512-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990475, version 1

Collections

Citation

Vida Dujmović, David R. Wood. On the Book Thickness of k-Trees. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.39--44. 〈hal-00990475〉

Partager

Métriques

Consultations de la notice

61

Téléchargements de fichiers

556