Book drawings of complete bipartite graphs

We recall that 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 page number of a graph G is the minimum k such that G admits a k-page embedding (that is, a k-page drawing with no edge crossings). The k-page crossing number v(k)(G) of G is the minimum number of crossings in a k-page drawing of G. We investigate the page numbers and k-page crossing numbers of complete bipartite graphs. We find the exact page numbers of several complete bipartite graphs, and use these page numbers to find the exact k-page crossing number of Kk+1,(n) for k is an element of {3, 4, 5, 6}. We also prove the general asymptotic estimate lim(k ->infinity) lim(n ->infinity) v(k)(K-k+1,K-n)/(2n(2)/k(2)) = 1. Finally, we give general upper bounds for v(k)(K-m,K-n), and relate these bounds to the k-planar crossing numbers of K-m,K-n and K-n. (C) 2013 Elsevier B.V. All rights reserved.