Rectilinear Crossing Number

The rectilinear crossing number of a graph is the minimum number of crossings in a straight line embedding of in a plane. It is variously denoted , (Schaefer 2017), , or .

It is sometimes claimed that the rectilinear crossing number is also known as the linear or geometric(al) crossing number, but evidence for that is slim (Schafer 2017).

A disconnected graph has a rectilinear crossing number equal to the sums of the rectilinear crossing numbers of its connected components.

When the (non-rectilinear) graph crossing number satisfies ,

(1)

(Bienstock and Dean 1993). While Bienstock and Dean don't actually prove equality for the case , they state it can be established analogously to . The result cannot be extended to , since there exist graphs with but for any (Bienstock and Dean 1993; Schaefer 2017, p. 54).

G. Exoo (pers. comm., May 11-12, 2019) has written a program which can compute rectilinear crossing numbers for cubic graphs up to around 20 vertices and up to 11 or 12 vertices for arbitrary simple graphs.

The smallest simple graphs for which occur on 8 nodes. The four such examples as summarized in the following table.

graph
16-cell graph	6	8
-Turán graph	9	10
8-double toroidal graph 8	9	10
complete graph	18	19

For a complete graph of order , the rectilinear crossing number is always larger than the general graph crossing number. For the complete graph with , 2, ..., is 0, 0, 0, 0, 1, 3, 9, 19, 36, 62, ... (OEIS A014540; White and Beineke 1978, Scheinerman and Wilf 1994). Although it had long been known that was either 61 or 62 (Singer 1971, Gardner 1986), it was finally proven to be 62 by Brodsky et al. (2000, 2001). The case was settled in 2004, and found to be 102. The Rectilinear Crossing Number Project (http://www.ist.tugraz.at/staff/aichholzer/crossings.html) has found all values for , and from very recent mathematical considerations, the rectilinear crossing numbers for and are also known. At the moment, the smallest value remaining unsettled is .

The following table summarizes known results (Rectilinear Crossing Number Project), and embeddings with minimal rectilinear crossing numbers are illustrated above (Read and Wilson 1998, pp. 282-283, with the erroneous embedding for corrected).

		non-isomorphic embeddings
3	0
4	0
5	1	1
6	3	1
7	9	3
8	19	2
9	36	10
10	62	2
11	102	374
12	153	1
13	229	4534
14	324	20
15	447	16001
16	603	36
17	798
18	1029
19	1318
20
21	2055	?
22		?
23		?
24		?
25		?

Upper limits have been provided by Singer (1971), who showed that

(2)

and Jensen (1971), who showed that

(3)

The best known bounds are given by

(4)

where . The upper bound is due to Aichholzer et al. (2002) and the lower bound to Lovász et al. (2004). A slightly weaker bound of was independently proved by Ábrego and Fernández-Merchand (2003). The small term in the lower bound is significant because it shows that the crossing number and the rectilinear crossing number of complete graphs differ in the leading term. In particular, it is known that there are non-rectilinear embeddings of with crossings (Moon 1965, Guy 1967).