A subpolynomial approximation algorithm for graph crossing number in low-degree graphs
A subpolynomial approximation algorithm for graph crossing number in low-degree graphs
We consider the classical Minimum Crossing Number problem: given an n-vertex graph G, compute a drawing of G in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently …