An algorithm for the graph crossing number problem

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 APX-hardness is known on the negative side.

Authors

• Julia Chuzhoy

Keywords

• approximation algorithm
• graph crossing number