ABSTRACT
The crossing number problem is hard, in a precise sense, as computational complexity theory tells us. Determining whether cr(G) ≤ k for a graph G and an integer k is NP-complete, a result first shown by Garey and Johnson [146] via a reduction from the optimal linear arrangement problem.
