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 (Pach and Tóth 2000).

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 are summarized in the following table. Minimal crossing and rectilinear crossing embeddings for the 16-cell graph and complete graph (Harary and Hill 1962-1963) are illustrated above.

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. Embeddings with minimal rectilinear crossing numbers are illustrated above for to 9 (Read and Wilson 1998, pp. 282-283, with the erroneous embedding for corrected).

For the complete graph with , 2, ..., is 0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... (OEIS A014540; White and Beineke 1978, Scheinerman and Wilf 1994, Ábrego et al. 2008). 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 , 20, and 22 through 27. At the moment, the smallest value remaining unsettled is , which has value either 7233 or 7234.

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

Letting

(5)

the best bounds known are

(6)

where is a binomial coefficient and the exact value of is not known (Finch 2003).

The rectilinear crossing number has an unexpected connection with Sylvester's four-point problem (Finch 2003).