The Crossing Number of the Complete Graph
The crossing number of is the minimum number of crossings in all drawings of in the plane.
(This discussion appears as [M].)
A drawing of a graph in the plane has the vertices represented by distinct points and the edges represented by polygonal lines joining their endpoints such that:
- no edge contains a vertex other than its endpoints,
- no two adjacent edges share a point other than their common endpoint,
- two nonadjacent edges share at most one point at which they cross transversally, and
- no three edges cross at the same point.
The conjectured value for the crossing number of is known to be an upper bound. This is shown by exhibiting a drawing with that number of crossings. If , place 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 we delete one vertex from the drawing described and achieve the conjectured minimum.
The conjecture is known to be true for at most 10 [G]. If the conjecture is true for , then it is also true for . This follows from an argument counting the number of crossings in drawings of all 's contained in an optimal drawing of .
It would also be interesting to prove that the conjectured upper bound is asymptotically correct, that is, that .
The best known lower bound is due to Kleitman [K], who showed that this limit is at least .
[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 , J. Combin. Theory 9 (1970) 315-323.
[M] B. Mohar, Problem of the Month
* indicates original appearance(s) of problem.