Computational search of small point sets with small rectilinear crossing number

Abstract

Let cr(K_n) 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(K_n) < 0.380473(n4)+Θ(n³); improving thus on the previous best known upper bound. This is done by obtaining new rectilinear drawings of K_n 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.