The Crossing Number of the Complete Graph

A drawing of a graph in the plane has the vertices placed at distinct points and the edges represented by homeomorphs of [0,1] joining their endpoints such that:

  1. no edge contains a vertex other than its endpoints,
  2. no two adjacent edges share a point other than their common endpoint, and
  3. two nonadjacent edges share at most one point at which they cross transversally.

The crossing number of G, cr(G), is the minimum number of pairwise crossings over all planar drawings.

Conjecture: Cr(K_n ) = (1/4) [n/2] [(n-1)/2] [(n-2)/2] [(n-3)/2] where [m] is the integer part of m.

This conjectured crossing number is known to be an upper bound. This is shown by exhibiting a drawing with the desired number of crossings. To wit, when n = 2m, place m vertices regularly spaced along both the top and bottom of a tin can (a cylinder homeomorphic to a sphere). Two vertices along the top are connected along the lid with a straight line segment. Likewise for two vertices along the bottom rim. A vertex on the top is connected to one on the bottom with a lateral line segment of minimum possible positive winding number around the cylinder. A count reveals that the number of crossings in this drawings 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 (see [G]). I believe it is also known to hold for n at most 12, but I am unsure of the reference. If the conjecture is true for n = 2m, then it is also true for n-1. This follows from an argument counting (with multiplicities) the number of crossings in a drawing of all K_{n-1}'s contained in an optimal drawing of K_n.

Some partial progress is possible by showing that the conjectured upper bound is asymptotically correct, that is, that lim cr(K_n)/n^4 = 1/64. The best known upper bound is due to Kleitman [K], who shows that this limit is at least 3/240. His result is based on a counting argument similar to that described above. This was recently improved, when [KPRS] showed that the crossing number of K_n is at least .83 of its conjectured value.

References

[G] 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.

[K] D. Kleitman, The crossing number of K_{5,n}, J. Combin. Theory 9 (1970) 315-323.

[KPRS] E. de Klerk, D. Pasechnik, R.B. Richter, and G. Salazar, personal communication.

Submitted by : Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA

Send comments to dan.archdeacon@uvm.edu

August, 1995, modified December 2003