最小化双向图中的交叉点数量

下列算法问题在我绘制图表时寻找不相关的东西：

我们有一个双面图的平面图，其中不相交的集合按照所示排列。 我们如何重新排列每列中的节点，以便边缘交叉点的数量最小化？ 我知道这个问题对于一般图（链接）来说是NP难的，但考虑到图是双方的，有一些技巧吗？

作为后续，如果有第三列w，它只有v边？ 还是进一步？

---

论文关于Hiroshi Nagamochi在一个双向图上的单边交叉最小化提到了Garey和Johnson关于交叉数的原始论文也证明了对于二部图而言，边交叉数最小化是NP难的。 事实上，即使您被告知一列的最佳订单，它仍然是NP难的：

给定二部图，2层图示包括将节点放置在直线L1上的第一节点集合V中并将节点放置在并行线路L2上的第二节点集合W中。 Harary和Schwenk首先介绍了最小化两层图纸中圆弧之间交叉数量的问题。 单边交叉最小化问题要求找到V中放置在L1上的节点的顺序，以使弧交叉的数量最小化（而L2中的W中的节点的顺序是给定的并且是固定的）。 这个问题的应用可以在VLSI布局和分层结构图中找到。

然而，Garey和Johnson以及Eades和Wormald分别表明双面和单面问题是NP难题。

---

Peter de Rivaz指出这是NP-Hard，但如果你有一些近似，你可以用下面的解决方案。

我最初的想法是使用一些基于力的算法进行图形布局，但实现起来可能有点繁琐。 但是，嘿，有这个美妙的程序graphviz.org，可以为你完成整个工作。

所以在安装完成之后，只需使用图形准备文件即可

graph G{
   {rank=same A B C D E}
   {rank=same F G H K I J}

    A -- F;
    A -- G;
    A -- K;
    A -- I;
    A -- H;
    A -- J;

    B -- G;

    C -- G;
    C -- J;

    D -- K;
    D -- I;
}

运行： dot -Tpng yourgraph -o yourgraph.png

并免费获得类似的东西:-)：

链接地址: http://www.djcxy.com/p/29221.html

上一篇: Minimizing number of crossings in a bipartite graph

下一篇: Networkx: Use common function for edge weight calculation