Crossing minimization in linear embeddings of graphs
S. Masuda, Kazuma Nakajima, Toshinobu Kashiwabara, Tomomi Fujisawa · IEEE Transactions on Computers · 1990
The problem of embedding a graph in the plane with the minimum number of edge crossings arises in some circuit layout problems. It has been known to be NP-hard in general. Recently, in the area of book embedding, this problem was shown to be NP-hard even when the vertices are placed on a straight line l. The authors show that the problem remains NP-hard even if, in addition to these constraints, the positions of the vertices on l are predetermined.>