A drawing of a graph G in the plane has the vertices represented by distinct points and the edges represented by polygonal lines joining their endpoints such that:
The crossing number cr(G) of G is the minimum number of crossings in all drawings of G in the plane.
Conjecture: cr(Kn) = 1/4 [ n/2 ] [ (n-1)/2 ] [ (n-2)/2] [ (n-3)/2 ] where [r] is the integer part of r.
This conjectured value for the crossing number of Kn is known to be an upper bound. This is shown by exhibiting a drawing with that number of crossings. If n = 2m, place m vertices regularly spaced along two circles of radii 1 and 2, respectively. Two vertices on the inner circle are connected by a straight line; two vertices on the outer circle are connected by a polygonal line outside the circle. A vertex on the inner circle is connected to one on the outer circle with a polygonal line segment of minimum possible positive winding angle around the cylinder. A simple count shows that the number of crossings in such a drawing achieves the conjectured minimum. For n = 2m-1 we delete one vertex from the drawing described and achieve the conjectured minimum.
The conjecture is known to be true for n at most 10 [1]. If the conjecture is true for n = 2m, then it is also true for n-1. This follows from an argument counting the number of crossings in drawings of all Kn-1's contained in an optimal drawing of Kn.
It would also be interesting to prove that the conjectured upper bound is asymptotically correct, that is, that lim cr(Kn) / (n4) = 3/8. The best known upper bound is due to Kleitman [2], who showed that this limit is at least 3/10.
References
[1] R. Guy, The decline and fall of Zarankiewicz's theorem, in Proof Techniques in Graph Theory (F. Harary Ed.), Academic Press, New York (1969) 63-69.
[2] D. Kleitman, The crossing number of K5,n , J. Combin. Theory 9 (1970) 315-323.
Send comments to Bojan.Mohar@uni-lj.si