Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990475
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:38:57 PM
Last modification on : Tuesday, February 6, 2018 - 2:48:02 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:17:23 PM

File

1778-6512-1-PB.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

107

Files downloads

1145