Book Thickness
The book thickness of a graph, also called fixed outerthickness, pagenumber (Endo 1997), page-number (Dong and Ma 2025), or stacknumber, is the minimum number of pages possible for a book embedding of the graph. It is denoted in various ways, including bt (Bernhart and Kainen 1979), p (Endo 1997, Dong and Ma 2025), and pn (Čunát 2013).
Constraints on a graph G with vertex count n and edge count include
![画像: [(m-n)/(m-3)]<=bt(G)<=[n/2]](/index.cgi/contrast/https://mathworld.wolfram.com/images/equations/BookThickness/NumberedEquation1.svg){kind=link}
(Bernhart and Kainen 1979).
A graph has book thickness 0 iff it has no edges (i.e., it is an empty graph). A graph has book thicknes 1 iff it is non-empty and outerplanar. A graph has book thickness at most 2 iff it is subhamiltonian. In particular, a graph has book thickness exactly 2 iff it is subhamiltonian but not outerplanar. Planar 3-trees have book thickness at most 3. Planar graphs have book thickness at most 4.
While every graph with book thickness 2 is planar, the Goldner-Harary graph (which has book thickness 3) provides an example of a planar graph that has book thickness >2.
Determining the book thickness of a given graph is an NP-hard problem.
For a graph with treewidth tw(G)=k,
(Dujmovic and Wood 2007).
Book thickness is related to graph thickness.
See also
Book Embedding, Book Graph, Graph Thickness, Outerplanar Graph, Subhamiltonian GraphExplore with Wolfram|Alpha
More things to try:
References
Bernhart, F. and Kainen, P. "THe Book Thickness of a Graph." J. Combin. Th. Ser. B 27, 320-33, 1979.Chung, F. R. K.; Leighton, F. T.; and Rosenberg, A. L. "Embedding Graph in Books: A Layout Problem With Applications to VLSI Design." SIAM J. Algebr. Disc. Meth. 8, 33-58, 1987.Čunát, V. "Hypercube Problems." Lecture 13. Oct. 1, 2013. https://ktiml.mff.cuni.cz/~gregor/hypercube/hypercubes_lec13.pdf.Dong, X. and Ma, D. "On the Page-Number of a Circulant Graph." AKCE Int. J. Graphs Combin. 22<,168-174, 2025.Dujmovic, V. and Wood, D. R. "Graph Treewidth and Geometric Thickness Parameters." Disc. Comput. Geom. 37, 641-670, 2007.Endo, T. "The Page Number of Toroidal Graphs Is at Most Seven." Disc. Math. 175, 87-96, 1997.Heath, L. S. "Algorithms for Embedding Graphs in Books." Ph.D. thesis. Chapel Hill, NC: University of North Carolina, 1985.Konoe, M.; Hagihara, K.; and Tokura, N. "Page-Number of Hypercubes and Cube-Connected Cycles." Systems and Computers in Japan 20, 34-47, 1989.Li, X. L. "Book Embedding of Graphs." Doctor's thesis. Zhengzhou University, 2002.Cite this as:
Weisstein, Eric W. "Book Thickness." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BookThickness.html