**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*)