在绘制不相关的图形时，发生了以下算法问题:
我们有一个二部图的平面图，其中不相交的集合按列排列。我们如何重新排列每一列中的节点，以使边缘交叉的数量最小化？我知道这个问题对于一般图(link)来说是NP难的，但是考虑到该图是二部图，是否有一些技巧？
作为后续，如果存在第三列w，而该列仅具有v的边，该怎么办？还是更进一步？
最佳答案
纸On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi
提到Garey和
约翰逊还证明了最大限度地减少过境点的数量
对于二部图是NP难的。实际上，它仍然是NP-hard
即使系统告知您某一列的最佳顺序:
关于algorithm - 最小化二部图中的交叉次数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20107645/