问题描述
以下算法问题在绘制图表时发现了一些不相关的内容：
我们有一个二部图的平面图，其中不相交的部分按照列显示。我们如何重新排列每列中的节点，以便边缘交叉点的数量最小化？我知道这个问题对普通图而言是NP难题（），但是有一些技巧考虑到该图是二部分的？
作为后续，如果存在第三列 w ，那么只有边 v ？或者更进一步？
具有较大程度提及由Garey和
约翰逊还证明，对于双边图，最小化边缘交叉点的数量
是NP难度。事实上，即使您被告知某一列的最佳订单，它仍然是NP难度
。
The following algorithm problem occurred to me while drawing a graph for something unrelated:
We have a plane drawing of a bipartite graph, with the disjoint sets arranged in columns as shown. How can we rearrange the nodes within each column so that the number of edge crossings is minimized? I know this problem is NP-hard for general graphs (link), but is there some trick considering that the graph is bipartite?
As a follow-up, what if there is a third column w, which only has edges to v? Or further?
The paper On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi mentions that the original paper on the crossing number by Garey and Johnson also proved that minimising the number of edge crossingsis NP-hard for bipartite graphs. In fact, it is still NP-hard even if you are told the optimal order for one column:
这篇关于最小化双向图中的交叉点数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！