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. 1. Graphs With Book Thickness bt(G) ≤ 1. The only graphs with bt(G) = 0 consist entirely of isolated vertices, since each edge of a graph must be assigned to a page. Observing that the vertices of the components C1, C2, . . . , Ck of a disconnected graph G can be grouped by components along the spine, it follows that bt(G) = max{bt(C1), bt(C2), . . . , bt(Ck)}. Hence, from this point forward, all graphs are assumed to be connected. Loops and multiple edges also do not complicate the book embedding problem. In a book embedding, a loop can be placed next to the spine and a single edge can be replaced by multiple copies without causing edge crossings. For simplicity, we will also restrict our discussion to simple graphs. It is easy to see that the set of one-page embeddable graphs includes paths. We embed the vertices along the spine according to the natural ordering of the path, v0, v1, . . . , vn. Now all edges {vi, vi+1} can be placed on a single page without crossing (see Figure 1). Not only paths, but all trees admit one-page embeddings. This is shown by induction on the number of vertices in the tree.