##
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.