Book drawings of complete bipartite graphs
We recall that a book with k k pages consists of a straight line (the spine ) and k 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 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 k -page drawing). The page number  of a graph G G is the minimum k k such that G G admits a k k -page embedding (that is, a k k -page drawing with no edge crossings). The k k -page crossing number ?k(G) ? k ( G ) of G G is the minimum number of crossings in a k k -page drawing of G G . We investigate the page numbers andk 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 exactk k -page crossing number of Kk+1,n K k + 1 , n for k?{3,4,5,6} k ? { 3 , 4 , 5 , 6 } . We also prove the general asymptotic estimate limk??limn???k(Kk+1,n)/(2n2/k2)=1 lim k ? ? lim n ? ? ? k ( K k + 1 , n ) / ( 2 n 2 / k 2 ) = 1 . Finally, we give general upper bounds for ?k(Km,n) ? k ( K m , n ) , and relate these bounds to the k k -planar crossing numbers of Km,n K m , n and Kn K n .
complete bipartite graphs 2-page crossing number book crossing number zarankiewicz conjecture