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 (Bernhart and Kainen 1979), (Endo 1997, Dong and Ma 2025), and (Čunát 2013).

Constraints on a graph with vertex count and edge count include

(1)

(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 .

Determining the book thickness of a given graph is an NP-hard problem.

For a graph with treewidth ,

(2)

(Dujmovic and Wood 2007).

Book thickness is related to graph thickness.