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

For a simple graph with vertex count and edge count , bounds include

(1)

(Bernhart and Kainen 1979), where is the ceiling function.

A graph has book thickness 0 iff it has no edges (i.e., it is an empty graph). A graph has book thickness 1 iff it has at least one graph edge and is outerplanar. A simple graph on at least three vertices 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. k-trees with that are planar 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.