Geodesic
Computational search of small point sets with small rectilinear crossing number
Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 3, pp. 393-399.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Let cr(Kn) be the minimum number of crossings over all rectilinear drawings of the complete graph on n vertices in the plane. In this paper we prove that cr(Kn) 0.380473(n4)+Θ(n3); improving thus on the previous best known upper bound. This is done by obtaining new rectilinear drawings of Kn for small values of n, and then using known constructions to obtain arbitrarily large good drawings from smaller ones. The "small" sets were found using a simple heuristic detailed in this paper. 
@article{JGAA_2014_18_3_a4,
     author = {Ruy Fabila-Monroy and Jorge L\'opez},
     title = {Computational search of small point sets with small rectilinear crossing number},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {393--399},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2014},
     doi = {10.7155/jgaa.00328},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00328/}
}
TY  - JOUR
AU  - Ruy Fabila-Monroy
AU  - Jorge López
TI  - Computational search of small point sets with small rectilinear crossing number
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 393
EP  - 399
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00328/
DO  - 10.7155/jgaa.00328
LA  - en
ID  - JGAA_2014_18_3_a4
ER  - 
%0 Journal Article
%A Ruy Fabila-Monroy
%A Jorge López
%T Computational search of small point sets with small rectilinear crossing number
%J Journal of Graph Algorithms and Applications
%D 2014
%P 393-399
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00328/
%R 10.7155/jgaa.00328
%G en
%F JGAA_2014_18_3_a4
Ruy Fabila-Monroy; Jorge López. Computational search of small point sets with small rectilinear crossing number. Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 3, pp. 393-399. doi : 10.7155/jgaa.00328. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00328/

Cité par Sources :