  A "book with k pages" consists of a straight line (the "spine") and k half-planes (the "pages"), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The k-page crossing number nu_k(G) of a graph G is the minimum number of crossings in a k-page drawing of G. In this paper we investigate the k-page crossing numbers of complete graphs K_n. We use semidefinite programming techniques to give improved lower bounds on nu_k(K_n) for various values of k. We also use a maximum satisfiability reformulation to calculate the exact value of nu_k(K_n) for several values of k and n. Finally, we investigate the best construction known for drawing K_n in k pages, calculate the resulting number of crossings, and discuss this upper bound in the light of the new results reported in this paper. 
Improved lower bounds on book crossing numbers of complete graphs