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

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

REFERENCES

Ábrego, B. M. and Fernández-Merchant, S. "A Lower Bound for the Rectilinear Crossing Number." Graphs and Comb. 21, 293-300, 2005.

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.

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. "Toward the Rectilinear Crossing Number of : New Drawings, Upper Bounds, and Asymptotics." http://www.cs.ubc.ca/spider/abrodsky/papers/reccr_n.ps.gz.Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of  is 62." 22 Sep 2000.

 http://arxiv.org/abs/cs.DM/0009023.Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of  is 62." Electronic J. Combinatorics 8, No. 1, R23, 1-30, 2001. 

http://www.combinatorics.org/Volume_8/Abstracts/v8i1r23.html.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: North-Holland, pp. 259-275, 1973.

Jensen, H. F. "An Upper Bound for the Rectilinear Crossing Number of the Complete Graph." J. Combin. Th. B 10, 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. Monthly 76, 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.

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. "The Graph Crossing Number and its Variants: A Survey." Elec. J. Combin., DS21, Version 3, Dec. 22, 2017.

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. Monthly 101, 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.S

loane, 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.