algorithm - 最小化二部图中的交叉数

Question

在为不相关的事物绘制图表时，我遇到了以下算法问题：

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

作为后续，如果有第三列w，它只有边缘到v怎么办？还是更进一步？

Answer 1

Hiroshi Nagamochi的论文On the one-lateral crossminimization in a big degree with large degree 提到 Garey 和 Johnson 关于交叉数的原始论文也证明了最小化边交叉的数量对于二部图是 NP-hard 的。事实上，即使你被告知一列的最佳顺序，它仍然是 NP-hard：

给定一个二分图，一个 2 层绘图包括将第一个节点集 V 中的节点放置在直线 L1 上，并将第二个节点集 W 中的节点放置在平行线 L2 上。Harary 和 Schwenk 首次提出了在 2 层绘图中最小化弧之间的交叉次数的问题。单边交叉最小化问题要求在 V 中找到要放置在 L1 上的节点的顺序，以便最小化弧交叉的数量（同时在 L2 上 W 中的节点的顺序是给定的并且是固定的）。该问题的应用可以在 VLSI 布局和层次图中找到。

然而，Garey 和 Johnson 以及 Eades 和 Wormald 分别证明了双边和单边问题是 NP 难的。

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

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