在二分图中减少交叉数量

Question

我在绘制一个与此无关的图形时遇到了以下算法问题：

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

作为后续，如果有第三列w，它只连接到v怎么办？或者更进一步呢？

- Imre Kerr

---

你想要两列（每个子图一个）还是节点可以以任意方式放置？ - artur grzesiak

你想要最优解还是近似解？（顺便说一句，好问题） - artur grzesiak

@arturgrzesiak 节点仍应该分为两列。我会编辑问题以使其更清晰。 - Imre Kerr

任何一种都会有所帮助。特别是人类可计算的算法（即我可以在手绘图形时使用的算法）将会非常好。 - Imre Kerr

Answer 1

这篇论文提到，Garey和Johnson的原始论文证明，在二分图中最小化边交叉数也是NP难问题。事实上，即使你知道一列的最佳顺序，仍然是NP难问题。论文题目为《Hiroshi Nagamochi关于具有大度数的二分图中单侧交叉最小化的论文》。请保留HTML标签。

给定一个二分图，一个二层绘图包括将第一节点集V上的节点放置在一条直线L1上，并将第二节点集W上的节点放置在平行线L2上。Harary和Schwenk最先提出了在二层绘图中最小化弧之间交叉数的问题。单侧交叉最小化问题要求找到在L1上放置节点V的顺序，以使弧交叉的数量最小化（同时在L2上给定并固定节点W的顺序）。该问题的应用可在VLSI布局和分层绘图中找到。但是，Garey和Johnson以及Eades和Wormald分别证明了两侧和单侧问题都是NP难问题。

- Peter de Rivaz

---

那篇论文看起来正是我所需要的。谢谢！ - Imre Kerr

Answer 2

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

然后你就可以免费获得类似下面的图片了 :-):

- artur grzesiak