
14.4. THICKNESS 475
only if it is outerplanar [BK79]. Bernhart and Kainen [BK79] proved that a graph has book
thickness at most two if and only if it is a subgr aph of a Hamiltonian planar graph. Unlike
thickness, being able to partition the edge set of a graph G into k outerplanar subgraphs
does not imply that G has book thickness at most k. For example, the edge set of K
5
can
be partitioned into two cycles, yet K
5
has book thickness more than two, since it is not a
subgraph of a Hamiltonian planar graph. The situation is similar for geometric thickness
as will soon become clear.
Book embeddings, first de fin ed by Ollmann [Oll73], are ubiquitous struct ...