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 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).
(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 (Bienstock and Dean 1993; Schaefer 2026, p. 85).
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 embedding
can be found in linear time. For a graph of graph order,
the embedding 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. The smallest examples and the associated subgraph-minimal
notion are discussed there.
For a complete graph of graph 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)
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 (Schaefer 2026, p. 86).
Upper bounds have been provided by Singer (1971),
who showed that
where the lower bound is due to Ábrego et al. (2012) and the upper bound to 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 embeddings of with crossings (Moon 1965, Guy 1967).
Ábrego, B. M.; Cetina, M.; Fernández-Merchant, S.; Leaños, J.; and Salazar, G. "On -Edges, Crossings, and Halving Lines of Geometric Drawings
of ."
Disc. Comput. Geom.48, 192-215, 2012. https://doi.org/10.1007/s00454-012-9403-y.Ábrego,
B. M. and Fernández-Merchant, S. "A Lower Bound for the Rectilinear
Crossing Number." Graphs and Comb.21, 293-300, 2005.Ábrego,
B. M.; Fernández-Merchant, S.; Leaños, J.; and Salazar, G. "The
Maximum Number of Halving Lines and the Rectilinear Crossing Number of for ." Elect. Notes Discr. Math30, 261-266,
2008.Aichholzer, O. "On the Rectilinear Crossing Number."
http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/.Aichholzer,
O.; Aurenhammer, F.; and Krasser, H. "On the Crossing Number of Complete Graphs."
In Proc. 18th Ann. ACM Symp. Comp. Geom., Barcelona, Spain, pp. 19-24,
2002.Biedl, T.; Chimani, M.; Derka, M.; and Mutzel, P. "Crossing
Number for Graphs with Bounded Pathwidth." Algorithmica82, 355-384,
2020. https://doi.org/10.1007/s00453-019-00653-x.Bienstock,
D. and Dean, N. "New Results on Rectilinear Crossing Numbers and Plane Embeddings."
J. Graph Th.16, 389-398, 1992.Bienstock, D. and Dean,
N. "Bounds for Rectilinear Crossing Numbers." J. Graph Th.17,
333-348, 1993.Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear
Crossing Number of Is 62." 22 Sep 2000. https://arxiv.org/abs/cs/0009023.Brodsky,
A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of Is 62." Elec. J. Combin.8, No. 1,
R23, 1-30, 2001. https://doi.org/10.37236/1567.Brodsky,
A.; Durocher, S.; and Gethner, E. "Toward the Rectilinear Crossing Number of
:
New Drawings, Upper Bounds, and Asymptotics." http://www.cs.ubc.ca/spider/abrodsky/papers/reccr_n.ps.gz.Cetina,
M.; Hernández-Vélez, C.; Leaños, J.; and Villalobos, C. "Point
Sets That Minimize -Edges, 3-Decomposable Drawings, and the Rectilinear
Crossing Number of ." Disc. Math.311, 1646-1657, 2011.
https://doi.org/10.1016/j.disc.2011.03.030.Fabila-Monroy,
R. and López, J. "Computational Search of Small Point Sets with Small
Rectilinear Crossing Number." J. Graph Algorithms Appl.18, 393-399,
2014. https://doi.org/10.7155/jgaa.00328.Finch,
S. R. "Rectilinear Crossing Constant." §8.18 in Mathematical
Constants. Cambridge, England: Cambridge University Press, pp. 532-534,
2003.Gardner, M. Knotted
Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman,
1986.Guy, R. K. "A Combinatorial Problem." NABLA (Bull.
Malayan Math. Soc.)7, 68-72, 1967.Guy, R. K. "Crossing
Numbers of Graphs." In Graph
Theory and Applications: Proceedings of the Conference at Western Michigan University,
Kalamazoo, Mich., May 10-13, 1972 (Ed. Y. Alavi, D. R. Lick,
and A. T. White). New York: Springer-Verlag, pp. 111-124, 1972.Harary,
F. and Hill, A. "On the Number of Crossings in a Complete Graph." Proc.
Edinburgh Math. Soc.13, 333-338, 1962/1963.Harary, F. and
Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey
of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands:
North-Holland, pp. 259-275, 1973.Jensen, H. F. "An Upper
Bound for the Rectilinear Crossing Number of the Complete Graph." J. Combin.
Th. B10, 212-216, 1971.Klee, V. "What Is the Expected
Volume of a Simplex Whose Vertices Are Chosen at Random from a Given Convex Body."
Amer. Math. Monthly76, 286-288, 1969.Lovász, L.;
Vesztergombi, K.; Wagner, U.; and Welzl, E. "Convex Quadrilaterals and -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. B80, 225-246, 2000.Read,
R. C. and Wilson, R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Rectilinear
Crossing Number Project. http://dist.ist.tugraz.at/cape5/.Schaefer,
M. Crossing Numbers of Graphs. Boca Raton, FL: CRC Press, 2018.Schaefer,
M. "The Graph Crossing Number and Its Variants: A Survey." Elec. J.
Combin., DS21, 9th ed., July 17, 2026. https://www.combinatorics.org/ojs/index.php/eljc/article/download/DS21/pdf.Scheinerman,
E. and Wilf, H. S. "The Rectilinear Crossing Number of a Complete Graph
and Sylvester's 'Four Point' Problem of Geometric Probability." Amer. Math.
Monthly101, 939-943, 1994.Singer, D. "The Rectilinear
Crossing Number of Certain Graphs." Unpublished manuscript, 1971. Quoted in
Gardner, M. Knotted
Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman,
1986.Sloane, N. J. A. Sequence A014540
in "The On-Line Encyclopedia of Integer Sequences."White,
A. T. and Beineke, L. W. "Topological Graph Theory." In Selected
Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson).
New York: Academic Press, pp. 15-49, 1978.Wilf, H. "On Crossing
Numbers, and Some Unsolved Problems." In Combinatorics,
Geometry, and Probability: A Tribute to Paul Erdős. Papers from the Conference
in Honor of Erdős' 80th Birthday Held at Trinity College, Cambridge, March 1993
(Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge
University Press, pp. 557-562, 1997.
is the minimum number of crossings in a straight
line embedding of 
in a plane. It is variously denoted
,
(Schaefer 2026), 
, 
, or 
(Pach and Tóth 2000).
,
,
they state it can be established analogously to 
. The crossing-number condition cannot be relaxed
to 
,
since there exist graphs 
with 
but 
for any 
(Bienstock and Dean 1993; Schaefer 2026, p. 85).
of consecutive bags containing the same three-vertex bag.
If 
is the number of vertices occurring in the bags of
,
then
denotes the floor function. Both this value and
a crossing-minimum straight line embedding
can be found in linear time. For a graph of graph order 
,
the embedding can be placed on a 
grid (Biedl et al.
2020).
are called curvy
graphs in this work. The smallest examples and the associated subgraph-minimal
notion are discussed there.
of graph 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).
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)
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 (Schaefer 2026, p. 86).
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 embeddings of 
with 
crossings (Moon 1965, Guy 1967).
is a binomial coefficient and the exact value
of 
is not known (Finch 2003).
-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.Aichholzer, O. "On the Rectilinear Crossing Number."
Is 62." 22 Sep 2000. 
Is 62." Elec. J. Combin. 8, No. 1,
R23, 1-30, 2001. 
:
New Drawings, Upper Bounds, and Asymptotics." 
-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.