$k$ distinct closed half planes, called [*pages*]{}, whose common boundary is $L$. If $p$ is a page, then $p = \{(0,y,z) : y,z \in \mathbb{R}, y \geq 0 \}$. The [*interior*]{} of a page $p$ is the open half plane, $p \setminus L$. A [*$k$-page book embedding*]{} is an embedding of a graph $G$ into a $k$-book such that:

-   each vertex $v \in V(G)$ is embedded into $L$;

-   each edge $e \in E(G)$ is either completely embedded into $L$, or all points of $e$ (except the endpoints) are embedded into the interior of a single page.

The [*spine order*]{}, for a particular book embedding, is the ordering of the vertices embedded into the spine whose $z$-coordinates are strictly increasing or decreasing. We can label the vertices embedded into the spine $v_1, v_2,..., v_n$. If two edges $v_iv_j$, with $i<j$ and $v_lv_m$, with $l<m$ are embedded into the same page, then it must be true that either $i<j<l<m$, $l<m<i<j$, $i<l<m<j$, or $l<i<j<m$. In this case, we say that the two edges follow the [*planarity rule*]{}. The [*book thickness of a graph*]{}, denoted $bt(G)$ is the minimum $k$ required for $G$ to have a $k$-page book embedding.

For a particular 