Abstract
It has been long conjectured that the crossing numbers of the complete bipartite graph K_{m,n} and of the complete graph K_n equal Z(m,n) (the value conjectured by Zarankiewicz, who came up with a drawing reaching this value) and Z(n) :=Z(n,n-2)/4, 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 v_2(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) v_2(Km,n) =Z(m,n), and (II) v_2(Kn) = 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 v_2 (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 v_2(K_n)/Z(n) >= 0.9253. The previous best-known lower bound involved the constant 0.8594.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.