最小化二分图中的交叉数

Question

在绘制不相关的图形时,我遇到了以下算法问题:

我们有一个二分图的平面绘图,其中不相交的集合按列排列,如图所示.我们如何重新排列每列中的节点,以便最小化边缘交叉的数量？我知道这个问题对于一般图形(链接)来说是NP难的,但考虑到图形是二分的,是否存在一些技巧？

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

Answer 1

论文关于Hirom Nagamochi的高度二分图中的单侧交叉最小化 提到了Garey和Johnson关于交叉数的原始论文也证明了最小化边缘交叉的数量对于二分图来说是NP难的.事实上,即使你被告知一列的最佳顺序,它仍然是NP难的:

给定二分图,2层图包括将第一节点集V中的节点放置在直线L1上并将第二节点集W中的节点放置在平行线L2上.Harary和Schwenk首先介绍了在2层图纸中最小化弧之间的交叉数量的问题.单侧交叉最小化问题要求找到V中的节点的排序以放置在L1上,以使弧交叉的数量最小化(同时给出并固定L2上的W中的节点的排序).问题的应用可以在VLSI布局和分层图中找到.

然而,Garey和Johnson以及Eades和Wormald分别表现出双方和片面的问题.

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

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