Graphs with small book thickness

In an article published in 1979, Kainen and Bernhart [1] laid the groundwork for further study of book embeddings of graphs. They define an n-book as a line L in 3-space, called the spine, and n half-planes, called pages, with L as their common boundary. An n-book embedding of a graph G is an embedding of G in an n-book so that the vertices of G lie on the spine and each edge of G lies within a single page so that no two edges cross. The book thickness bt(G) or page number pg(G) of a graph G is the smallest n so that G has an n-book embedding. Finding the book thickness of an arbitrary graph is a difficult problem. Even with a pre-specified vertex ordering, the problem has been shown to be NP-complete [6]. In this paper we will introduce book embeddings with particular focus on results for graphs with small book thickness.