On the Book Thickness of k-Trees

Article, Preprint English OPEN
Dujmović , Vida ; Wood , David R. (2011)
  • Publisher: DMTCS
  • Subject: Mathematics - Combinatorics | [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM] | 05C62, 68R10

Graphs and Algorithms; International audience; Every 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.
  • References (13)
    13 references, page 1 of 2

    F. R. Bernhart and P. C. Kainen. The book thickness of a graph. J. Combin. Theory Ser. B, 27(3):320-331, 1979. doi:10.1016/0095-8956(79)90021-2.

    G. A. Cottafava and O. D'Antona. Book-thickness and book-coarseness of graphs. In Proc. 5th International Symp. on Network Theory (Sarajevo), pages 337-340, 1984.

    E. Di Giacomo, W. Didimo, G. Liotta, and S. K. Wismath. Book embeddability of series-parallel digraphs. Algorithmica, 45(4):531-547, 2006. doi:10.1007/s00453-005-1185-7.

    R. Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, 2nd edition, 2000. http://diestel-graph-theory.com/.

    V. Dujmovic´ and D. R. Wood. Graph treewidth and geometric thickness parameters. Discrete Comput. Geom., 37(4):641-670, 2007. doi:10.1007/s00454-007-1318-7.

    V. Dujmovic´ and D. R. Wood. On linear layouts of graphs. Discrete Math. Theor. Comput. Sci., 6(2):339- 358, 2004. http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/ 193.

    J. L. Ganley and L. S. Heath. The pagenumber of k-trees is O(k). Discrete Appl. Math., 109(3):215-221, 2001. doi:10.1016/S0166-218X(00)00178-5.

    C. D. Keys. Graphs critical for maximal bookthickness. Pi Mu Epsilon J., 6:79-84, 1975.

    L. T. Ollmann. On the book thicknesses of various graphs. In F. Hoffman, R. B. Levow, and R. S. D. Thomas, editors, Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, volume VIII of Congr. Numer., page 459. Utilitas Math., 1973.

    S. Rengarajan and C. E. Veni Madhavan. Stack and queue number of 2-trees. In D.-Z. Du and M. Li, editors, Proc. 1st Annual International Conf. on Computing and Combinatorics (COCOON '95), volume 959 of Lecture Notes in Comput. Sci., pages 203-212. Springer, 1995. doi:10.1007/BFb0030834.

  • Metrics
    No metrics available
Share - Bookmark