  We study the Minimum Crossing Number problem: given an $n$-vertex graph $G$,
the goal is to find a drawing of $G$ in the plane with minimum number of edge
crossings. This is one of the central problems in topological graph theory,
that has been studied extensively over the past three decades. The first
non-trivial efficient algorithm for the problem, due to Leighton and Rao,
achieved an $O(n\log^4n)$-approximation for bounded degree graphs. This
algorithm has since been improved by poly-logarithmic factors, with the best
current approximation ratio standing on $O(n \poly(d) \log^{3/2}n)$ for graphs
with maximum degree $d$. In contrast, only APX-hardness is known on the
negative side.
  In this paper we present an efficient randomized algorithm to find a drawing
of any $n$-vertex graph $G$ in the plane with $O(OPT^{10}\cdot \poly(d \log
n))$ crossings, where $OPT$ is the number of crossings in the optimal solution,
and $d$ is the maximum vertex degree in $G$. This result implies an
$\tilde{O}(n^{9/10} \poly(d))$-approximation for Minimum Crossing Number, thus
breaking the long-standing $\tilde{O}(n)$-approximation barrier for
bounded-degree graphs.
