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