https://hal.inria.fr/hal-00990475Dujmović, VidaVidaDujmovićSchool of Computer Science [Ottawa] - Carleton UniversityWood, David R.David R.WoodDepartment of Mathematics and Statistics [Melbourne] - University of MelbourneOn the Book Thickness of k-TreesHAL CCSD2011[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Inria Sophia Antipolis-Méditerranée / I3s, Service Ist2014-05-13 15:38:572018-02-06 14:48:022014-05-13 16:18:30enJournal articleshttps://hal.inria.fr/hal-00990475/document10.46298/dmtcs.550application/pdf1Every 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.