The Crossing Number of the Complete Bipartite Graph

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:

• 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 crossing number cr(G) of G is the minimum number of crossings in all drawings of G in the plane.

Conjecture: cr(K_m,n) = [ m/2 ] [ (m-1)/2 ] [ n/2 ] [ (n-1)/2 ]  where [r] is the integer part of r.

This problem is also known as Turan's Brickyard Problem (since it was formulated by Turan when he was working at a brickyard - the edges of the drawing would correspond to train tracks connecting different shipping depots, and fewer crossings would mean smaller chance for collision of little trains and smaller chance for their derailing).

This conjectured value for the crossing number of K_m,n can be realized by the following drawing. Place n/2 vertices on the positive x-axis and n/2 vertices on the negative x-axis (or (n+1)/2 and (n-1)/2, respectively, if n is odd), and m/2 vertices along the positive and negative y-axis (again, splitting nearly equally if m is odd). Now connect each pair of vertices on different axes with straight line segments.

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 K_5,n , J. Combin. Theory 9 (1970) 315-32

Send comments to Bojan.Mohar@uni-lj.si

Revised: junij 15, 2001.