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

A graph with vertex count has book thickness no greater than .

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 .

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

Book thickness is related to graph thickness.