52 citations · 118 across the 27 of their papers we have counts for
Showing 2012 · cs.CGShow all
2 papers · 2 filters
cs.CG2012
Hardness of approximation for crossing number
Sergio Cabello
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.
cs.CG2012
Adding one edge to planar graphs makes crossing number and 1-planarity hard
Sergio Cabello, Bojan Mohar
A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show the surprising fact that it is NP-hard to compute the crossing number of near-planar gra…