### On the Book Thickness of k-Trees

*Vida Dujmović, David Wood*

#### Abstract

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.Full Text: PDF PostScript