The rectilinear crossing number of a simple graph 
is the minimum number of pairs of edges
whose interiors cross in a straight line drawing
of 
in the plane, with its vertices
in general position, meaning that no three are
collinear. It is variously denoted 
, 
(Schaefer 2026), 
, 
, 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 (Schaefer 2026).
A disconnected graph has a rectilinear crossing number equal to the sum 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 do not actually prove equality for the case 
,
they state it can be established analogously to 
. The crossing-number condition cannot be relaxed
to 
,
since there exist graphs 
with 
but 
for any integer 
(Bienstock and Dean 1993; Schaefer 2026, p. 86).
The Hernández-Vélez-Leaños-Salazar graphs give an explicit construction with graph
crossing number 
and rectilinear crossing number at least 
for integers 
(Hernández-Vélez et al. 2017,
Theorem 2).
Equality also holds for maximal graphs of pathwidth 3, where "maximal" means that adding any missing graph
edge makes the pathwidth exceed 3. An alternating
width-3 path decomposition, whose bags alternate in size between 4 and 3, can be
partitioned into maximal clusters 
of consecutive bags containing the same three-vertex bag.
If 
is the number of vertices occurring in the bags of
,
then
 |
(2)
|
Here 
denotes the floor function. Both this value and
a crossing-minimum straight line drawing
can be found in linear time. For a graph of graph
order 
,
the drawing can be placed on a 
grid (Biedl et al.
2020).
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.
Graphs for which 
are called curvy
graphs in this work. A minimally curvy graph
contains no curvy graph as a proper topological
minor.
For a complete graph 
of graph order 
, the rectilinear crossing number is always larger than
the general graph crossing number. Drawings
with minimal rectilinear crossing numbers are illustrated above for 
to 9 (Read and Wilson 1998, pp. 282-283, with the erroneous
drawing 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). Aichholzer et al. (2002) determined 
.
The Rectilinear Crossing Number Project (http://www.ist.tugraz.at/staff/aichholzer/crossings.html)
and subsequent work have determined the values for all 
. In addition, the rectilinear crossing number of 
is 9726 (Cetina et al. 2011). The smallest unresolved case is 
, for which 
is either 7233 or 7234 (OEIS A014540).
Upper bounds have been provided by Singer (1971), whose recursive construction gives
 |
(3)
|
for 
,
where 
is a positive integer (Brodsky et al. 2003,
p. 67), and Jensen (1971), who showed that
 |
(4)
|
The best known bounds are given by
 |
(5)
|
where the lower bound is due to Ábrego et al. (2012) and the upper bound to Aichholzer et
al. (2020), improving the earlier upper bound
of Fabila-Monroy and López (2014). The strict improvement over 
in the lower bound
is significant because it shows that the graph
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 drawings of 
with 
crossings (Moon 1965, Guy 1967).
The ratios 
form a nondecreasing bounded sequence for 
,
so their limit exists (Schaefer 2026, p. 87). Letting
 |
(6)
|
the best bounds known are
 |
(7)
|
where 
is a binomial coefficient (Finch 2003, Aichholzer
et al. 2020). The exact value of 
is not known.
The rectilinear crossing number has an unexpected connection with Sylvester's four-point problem (Finch 2003).
For the balanced complete bipartite graph 
,
Balogh et al. (2026) proved
 |
(8)
|
Here 
is the floor function. This strengthens the asymptotic
lower bound toward Zarankiewicz's
conjecture in the rectilinear setting. Balogh et al. (2026) report ChatGPT
assistance with correctness checks in part of the proof.
-Edges, Crossings, and Halving Lines of Geometric Drawings
of 
."
Disc. Comput. Geom. 48, 192-215, 2012. 
for 
." Elect. Notes Discr. Math. 30,
261-266, 2008. 
Is 62." 22 Sep 2000. 
Is 62." Elec. J. Combin. 8, No. 1,
R23, 2001. 
:
New Drawings, Upper Bounds, and Asymptotics." Disc. Math. 262,
59-77, 2003. 
-Edges, 3-Decomposable Drawings, and the Rectilinear
Crossing Number of 
." Disc. Math. 311, 1646-1657, 2011.
-Sets."
In Towards a Theory of Crossing Numbers (Ed. J. Pach). Providence, RI:
Amer. Math. Soc., pp. 139-148, 2004.Moon, J. "On the Distribution
of Crossings in Random Complete Graphs." J. Soc. Indust. Appl. Math. 13,
506-510, 1965.Pach, J. and Tóth, G., "Which Crossing Number
Is It Anyway?" J. Combin. Theory Ser. B 80, 225-246, 2000.Read,
R. C. and Wilson, R. J.