Every k-tree has book thickness at most k + 1, and this bound is best possible for all k ≥ 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 ≥ 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.

Additional Metadata
Keywords Book embedding, Book thickness, Graph, Pagenumber, Stacknumber, Tree decomposition, Treewidth
Journal Discrete Mathematics and Theoretical Computer Science
Citation
Dujmović, V, & Wood, D. (2011). On the book thickness of k-trees. Discrete Mathematics and Theoretical Computer Science, 13(3), 39–44.