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 4 n´-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 APXhardness 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 · 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Õ " n 9/10 · poly(d) " -approximation for Minimum Crossing Number, thus breaking the long-standingÕ(n)-approximation barrier for bounded-degree graphs.
The best currently known algorithm implies an O(n 9/10 )-approximation for the minimum crossing number on graphs having bounded maximum degree REF .
An algorithm for the graph crossing number problem
STOC '11
Mathematics Computer Science