cp's OEIS Frontend

A014540 Rectilinear crossing number of complete graph on n nodes.

%I A014540 #38 Feb 16 2025 08:32:33
%S A014540 0,0,0,0,1,3,9,19,36,62,102,153,229,324,447,603,798,1029,1318,1657,
%T A014540 2055,2528,3077,3699,4430,5250,6180
%N A014540 Rectilinear crossing number of complete graph on n nodes.
%C A014540 The values a(19) and a(21) were obtained by Aichholzer et al. in 2006. The value a(18) is claimed by the Rectilinear Crossing Number project after months of distributed computing. This was confirmed by Abrego et al., they also found the values a(20) and a(22) to a(27). The next unknown entry, a(28), is either 7233 or 7234. - Bernardo M. Abrego (bernardo.abrego(AT)csun.edu), May 05 2008
%D A014540 Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 8.18, p. 532.
%D A014540 M. Gardner, Crossing Numbers. Ch. 11 in Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, 1986.
%D A014540 C. Thomassen, Embeddings and minors, pp. 301-349 of R. L. Graham et al., eds., Handbook of Combinatorics, MIT Press.
%H A014540 B. M. Abrego, S. Fernandez-Merchant, J. Leaños, and G. Salazar, <a href="http://dx.doi.org/10.1016/j.endm.2008.01.045">The maximum number of halving lines and the rectilinear crossing number of K_n for n <= 27</a>, Electronic Notes in Discrete Mathematics, 30 (2008), 261-266.
%H A014540 O. Aichholzer, <a href="http://www.ist.tugraz.at/staff/aichholzer/crossings.html">Crossing number project</a>.
%H A014540 O. Aichholzer, F. Aurenhammer, and H. Krasser, <a href="http://www.igi.TUGraz.at/oaich/psfiles/aak-prcn-01.ps.gz">Progress on rectilinear crossing numbers</a>. [Broken link]
%H A014540 O. Aichholzer, F. Aurenhammer, and H. Krasser, <a href="http://www.igi.tugraz.at/Abstracts/aak-prcn-01/">Progress on rectilinear crossing numbers</a>, Technical report, IGI-TU Graz, Austria, 2001.
%H A014540 O. Aichholzer, F. Aurenhammer, and H. Krasser, <a href="http://www.igi.TUGraz.at/oaich/triangulations/crossing.html">On the Rectilinear Crossing Number</a>. [Broken link]
%H A014540 O. Aichholzer, J. Garcia, D. Orden, and P. Ramos, <a href="http://dx.doi.org/10.1007/s00454-007-1325-8">New lower bounds for the number of <= k-edges and the rectilinear crossing number of K_n</a>, Discrete & Computational Geometry 38 (2007), 1-14.
%H A014540 O. Aichholzer and H. Krasser, <a href="http://www.ist.tugraz.at/publications/oaich/psfiles/ak-psotd-01.ps.gz">The point set order type data base: a collection of applications and results</a>, pp. 17-20 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001. [Broken link]
%H A014540 D. Archdeacon, <a href="http://www.emba.uvm.edu/~archdeac/problems/rectcros.htm">The rectilinear crossing number</a>.
%H A014540 D. Bienstock and N. Dean, <a href="http://dx.doi.org/10.1002/jgt.3190170308">Bounds for rectilinear crossing numbers</a>, J. Graph Theory 17 (1993) 333-348
%H A014540 A. Brodsky, S. Durocher, and E. Gethner, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v8i1r23">The Rectilinear Crossing Number of K_{10} is 62</a>, The Electronic J. Combin, #R23, 2001.
%H A014540 A. Brodsky, S. Durocher, and E. Gethner, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00491-0">Toward the rectilinear crossing number of K_n: new drawings, upper bounds, and asymptotics</a>, Discrete Math. 262 (2003), 59-77.
%H A014540 D. Garber, <a href="http://arXiv.org/abs/math.CO/0303317">The Orchard crossing number of an abstract graph</a>, arXiv:math/0303317 [math.CO], 2003-2009.
%H A014540 H. F. Jensen, <a href="http://dx.doi.org/10.1016/0095-8956(71)90045-1">An Upper Bound for the Rectilinear Crossing Number of the Complete Graph</a>, J. Comb. Th. Ser. B 10, 212-216, 1971.
%H A014540 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphCrossingNumber.html">Graph Crossing Number</a>.
%H A014540 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RectilinearCrossingNumber.html">Rectilinear Crossing Number</a>.
%H A014540 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ZarankiewiczsConjecture.html">Zarankiewicz's Conjecture</a>.
%Y A014540 Cf. A000241, A030179, A006247.
%K A014540 nonn,nice,hard,more
%O A014540 1,6
%A A014540 _Eric W. Weisstein_
%E A014540 102 from Oswin Aichholzer (oswin.aichholzer(AT)tugraz.at), Aug 14 2001
%E A014540 153 from Hannes Krasser (hkrasser(AT)igi.tu-graz.ac.at), Sep 17 2001
%E A014540 More terms from _Eric W. Weisstein_, Nov 30 2006
%E A014540 More terms from Bernardo M. Abrego (bernardo.abrego(AT)csun.edu), May 05 2008