Approximating the Rectilinear Crossing Number

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G,cr(G), is the minimum number of pairs of crossing edges in any straight-line drawing of G. Determining or estimating cr¯(G) appears to be a difficult problem, and deciding if cr¯(G)≤k is known to be NP-hard. In fact, the asymptotic behavior of cr¯(Kn) is still unknown. In this paper, we present a deterministic n2+o(1)-time algorithm that finds a straight-line drawing of any n-vertex graph G with cr¯(G)+o(n^4) pairs of crossing edges. Together with the well-known Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any dense n-vertex graph G, one can efficiently find a straight-line drawing of G with (1+o(1))cr¯(G) pairs of crossing edges