Improved lower bounds for the 2-page crossing numbers of K _m,n and K _n via semidefinite programming

It has long been conjectured that the crossing numbers of the complete bipartite graph K _m,n and of the complete graph K _n equal Z(m, n) := ⌊n/2⌋ ⌊n-1/2⌋ ⌊m/2⌋ ⌊m-1/2⌋ and Z(n) := 1/4 ⌊n/2⌋ ⌊n-1/2⌋ ⌊n-2/2⌋ ⌊n-3/2⌋, respectively. In a 2-page drawing of a graph, the vertices are drawn on a straight line (the spine), and each edge is contained in one of the half-planes of the spine. The 2-page crossing number ν ₂(G) of a graph G is the minimum number of crossings in a 2-page drawing of G. Somewhat surprisingly, there are 2-page drawings of K _m,n (respectively, K _n) with exactly Z(m, n) (respectively, Z(n)) crossings, thus yielding the conjectures (I) ν ₂(K _m,n) ?= Z(m, n) and (II) ν ₂(K _n) ?= Z(n). It is known that (I) holds for min{m, n} ≤ 6, and that (II) holds for n ≤ 14. In this paper we prove that (I) holds asymptotically (that is, lim _n-∞ ν ₂(K _m,n)/Z(m, n) = 1) for m = 7 and 8. We also prove (II) for 15 ≤ n ≤ 18 and n ε {20, 24}, and establish the asymptotic estimate lim _n-∞ ν ₂(Kn)/ Z(n) ≥ 0.9253. The previous best-known lower bound involved the constant 0.8594.