Crossing Number is NP-Complete
Michael R. Garey, David S. Johnson · SIAM Journal on Algebraic and Discrete Methods · 1983
In this paper we consider a problem related to questions of optimal circuit layout: Given a graph or network, how can we embed it in a planar surface so as to minimize the number of edge-crossings? We show that this problem is NP-complete, and hence there is not likely to be any efficient way to design an optimal embedding.