A drawing of a graph G in the plane allows edges to cross. The crossing number cr(G) is the fewest number of pairwise edge crossings taken over all drawings of G. In a rectilinear drawing the edges must all be line segments. The fewest number of crossings in such a drawing is the rectilinear crossing number crbar(G). Clearly crbar(G) is at least cr(G). Strict inequality can hold. For example, Richard

Guy has shown that crbar(K(8)) > cr(K(8)) = 18. A similar inequality holds for K(10), but not for K(9). It is believed that crbar(K(n)) > cr(K(n)) for all n at least 10.

Problem: Find the rectilinear crossing number of the complete graph.

The best result is due to Jensen [J] who showed that an upper bound on crbar(K(n)) is

[(7 n^4 - 56 n^3 + 128 n^2 + 48 n)[(n-7)/3] + 108)/432]

where [x] represents the integer part of x.

It was conjectured that this inequality might be an equality, but Jensen reports that he has found several better drawings. In particular, he reports that crbar(K(n)) < n^4/63 for large n.

Problems: Find lim crbar(K(n))/n^4. Find lim crbar(K(n))/cr(K_n).

Both limits are as n approaches infinity. The second limit is conjectured to be 1.

In contrast to the complete graph, it is thought that the rectilinear crossing number of the complete bipartite graph is equal to its crossing number.

Bienstock and Dean [BD] have found infinitely many graphs with crossing number 4 but with strictly larger rectilinear crossing number. The value 4 is the smallest possible.

[BD] D. Bienstock and N. Dean, Bounds for rectilinear crossing numbers, J. Graph Theory 17 (1993) 333-348.

[J] H.F. Jensen, An upper bound for the rectilinear crossing number of the complete graph, J. Combin. Theory B 10(1971) 212-216.

Submitted by: Dan Archdeacon, Department of

Mathematics and Statistics, University of Vermont, Burlington VT

05405 USA.