An Algorithm for the Graph Crossing Number Problem

Understand

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$.