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) over bar (G), is the minimum number of pairs of crossing edges in any straight-line drawing of G. Determining or estimating (cr) over bar (G) appears to be a difficult problem, and deciding if (cr) over bar (G) <= k is known to be NP-hard. In fact, the asymptotic behavior of (cr) over bar (K-n) is still unknown. In this paper, we present a deterministic n(2+o(1))-time algorithm that finds a straight-line drawing of any n-vertex graph G with ((cr) over barG)+ 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) over bar (G) pairs of crossing edges. (C) 2019 Elsevier B.V. All rights reserved.