  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$,
$\overline{cr}(G)$, is the minimum number of crossing edges in any
straight-line drawing of $G$. Determining or estimating $\overline{cr}(G)$
appears to be a difficult problem, and deciding if $\overline{cr}(G)\leq k$ is
known to be NP-hard. In fact, the asymptotic behavior of $\overline{cr}(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
$\overline{cr}(G) + o(n^4)$ 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))\overline{cr}(G)$ crossing edges.
