The Rectilinear Crossing Number



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} (crbar(K_{10}) = 62 as determined but by Brodsky et al). 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 published 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.

A nice recent result is due to Bernardo Abrego and Sylvia Fernandez-Marchant [AF] who proved that crbar(K_n) is at least (1/4) \floor(n/2) \floor((n-1)/2) \floor((n-2)/2) \floor((n-3)/2). This number is the conjectured value for the crossing number of K_n in the more general case that the edges need not be line segments. For a lower bound on this parameter,

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

Both limits are as n approaches infinity.

Related to the first limit, define c = lim crbar(K_n) / (n choose 4). Uli Wagner reports that some (unpublished?) work by David Singer in 1971 improves the upper bound on c to 5/312, which is better than the limit derived from  Jensen's bound. Subsequent work by Brodsky on the rectilinear crossing number of K_{10} improved this bound to .3001 < c < .3838 [B]. Aicholzer et al. calculated crbar(K_{12}} which improves the bounds to .3115 < c < .3804. The lower bound was subsequently improved to c > .3288 in [1]. Wagner et al has recently showed that crbar(K_n) is at least (3/8 + epsilon) (n choose 4), placing an asymptotic gap between this parameter and the usual crossing number. Specifically, c > 3/8 + epsilon > .37501 where epsilon is greater than approximately 1.0887  times  10^{-5}.

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.

References:

[1] On the rectilinear crossing number of complete graphs

[2] Convex quadrilaterals and k-sets

[AF] B. Abrego and S. Fernandez-Marchant, personal communication

[BDG] A. Brodsky, S. Durocher, and E. Gethner, Towards the rectilinear crossing number of K_n: new drawings, upper bounds, and asymptotics, Discrete Mathematics 262 (2003) 59-77.

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

[W] Wagner, I don't know this reference, but he gave a talk at the SODA conference in Baltimore (it might be [1] or [2]).


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, updated December 2003 (with thanks to Uli Wagner, uli@inf.ethz.ch G. Salazar salazar@math.ohio-state.edu and to D. Eppstein eppstein@ics.uci.edu)