Discrete Mathematics & Theoretical Computer Science, Vol 13, No 3 (2011)

Font Size:  Small  Medium  Large

On the Book Thickness of k-Trees

Vida Dujmović, David Wood


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