在为不相关的事物绘制图形时，我遇到了以下算法问题:
我们有一个二分图的平面图，如图所示，不相交的集合按列排列。我们如何重新排列每列中的节点，以使边缘交叉的数量最小化？我知道这个问题对于一般图 ( link ) 是 NP-hard 问题，但是考虑到该图是二分图，是否有一些技巧？
作为后续，如果有第三列 w，它只有 v 的边怎么办？还是更远？
最佳答案
论文On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi 提到 Garey 和 约翰逊还证明，最小化边交叉的数量 对于二分图是 NP 难的。其实还是NP难的 即使您被告知一列的最佳顺序:
Given a bipartite graph, a 2-layered drawing consists of placing nodes in the first node set V on a straight line L1 and placing nodes in the second node set W on a parallel line L2. The problem of minimizing the number of crossings between arcs in a 2-layered drawing was first introduced by Harary and Schwenk. The one-sided crossing minimization problem asks to find an ordering of nodes in V to be placed on L1 so that the number of arc crossings is minimized (while the ordering of the nodes in W on L2 is given and fixed). Applications of the problem can be found in VLSI layouts and hierarchical drawings.
However, the two-sided and one-sided problems are shown to be NP-hard by Garey and Johnson and by Eades and Wormald , respectively.
关于algorithm - 最小化二分图中的交叉数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20107645/