Hardness of approximation for crossing number

Abstract

We show that, if P\not=NP, there is a constant c > 1 such that there is no c-approximation algorithm for the crossing number, even when restricted to 3-regular graphs.

10 pages, 4 figures