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.
No takes yet. Share an insight, caveat, or question.
Garey et al. (1983) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: