On the Rectilinear Crossing Number

The following table contains lower bounds and best known minimizing examples (upper bounds) for the rectilinear crossing number of the complete graph of a set of n points in the plane (in general position; n up to 100). For details please refer to our publications.

For the computation of the lower bounds we used a Mathematica-notebook, which you can download here to make your own experiments.

One implication of the investigation of small sets is an improved constant for the asymptotic upper bound for the rectilinear crossing number. Using Theorem 2 of [B.Abrego, S.Fernandez-Merchant: Geometric drawings of K_n with few crossings.] and plugging in the values for n=90 below, we get an upper bound of 0.38054415*(n choose 4) + O(n^3), the best currently known bound.

Several of the lower bounds are summarized from recent papers. Tight values for up to n=27 are from [The maximum number of halving lines and the rectilinear crossing number of K_n for n<=27, Bernardo M. Abregoa, Silvia Fernandez-Merchanta, Jesus Leanosb and Gelasio Salazar, Electronic Notes in Discrete Mathematics, 30:261--266, 2008].

The last column contains the number of all existing combinatorial non-isomorphic minimal drawings and a binary file of them (for n up to 16) and all sets we found so far for n = 17 to 20. The xy-coordinates are stored as 16-bit unsigned integer, see our order type page for more details on the file format.

Table last modified on Tue, 19 May 2009 14:47:22 +0000.