Hardness of approximation for crossing number
  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. 
Sergio Cabello
cs.CG cs.CC math.CO