Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00328
Computational search of small point sets with small rectilinear crossing number
Ruy Fabila-Monroy and Jorge López
Vol. 18, no. 3, pp. 393-399, 2014. Regular paper.
Abstract 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.
Submitted: March 2014.
Reviewed: May 2014.
Revised: May 2014.
Accepted: June 2014.
Final: June 2014.
Published: June 2014.
Communicated by Csaba D. Tóth
article (PDF)
BibTeX