最小化双向图中的交叉点数量 [英] Minimizing number of crossings in a bipartite graph
问题描述
以下算法问题在绘制图表时发现了一些不相关的内容：
我们有一个二部图的平面图，其中不相交的部分按照列显示。我们如何重新排列每列中的节点，以便边缘交叉点的数量最小化？我知道这个问题对普通图而言是NP难题（链接），但是有一些技巧考虑到该图是二部分的？
作为后续，如果存在第三列 w ，那么只有边 v ？或者更进一步？
关于双边图中的单边交叉点最小化
由Hiroshi
Nagamochi
具有较大程度提及由Garey和
约翰逊还证明，对于双边图，最小化边缘交叉点的数量
是NP难度。事实上，即使您被告知某一列的最佳订单，它仍然是NP难度
。
鉴于双方图，2层图示包括将节点
放置在直线L1上的第一节点集合V中，并将节点放置在并行线路L2上的
第二节点集合W中。最小化
两层图纸中圆弧之间交叉点数量的问题是由Harary和Schwenk首先引入的
。单边交叉最小化
问题要求找到V中的节点的顺序以便放置在L1上，使
使弧交叉的数量最小化（而
的节点的排序L2上的W是固定的）。问题
的应用程序可以在VLSI布局和层次结构图中找到。
然而，双面和单面问题被证明是NP-由Garey和Johnson以及Eades和Wormald分别为
。
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 crossings is NP-hard for bipartite graphs. In fact, it is still NP-hard even if you are told the optimal order for one column:
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.
这篇关于最小化双向图中的交叉点数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
