最小化在二部圖口岸的數量

Question

下面的算法問題發生在我身上，同時繪製圖形的東西無關：

我們有一個二分圖的平面圖紙，與設置在獨立集合如圖所示。我們如何重新排列每列中的節點，以便邊緣交叉點的數量最小化？我知道這個問題對於普通圖（link）是NP-hard，但考慮到圖是雙方的，有一些技巧嗎？

作爲後續，如果有什麼是第三列瓦特，其中只有邊緣v？還是進一步？

Answer 1

本文On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi 提到由Garey和 約翰遜的交叉數的原始紙也證明，最小化邊交叉 的數目是NP難題爲二分圖。事實上，它仍然是NP難 即使你被告知的最優順序的一列：

給定一個二分圖，一個2層圖紙由上放置節點 的第一個節點集V的直線L1並將節點放置在平行線L2上的第二節點集合W上。最小化2層圖紙中圓弧之間交叉點的數量的問題首先由Harary和Schwenk介紹，其中 。單邊交叉最小化問題要求找到V中要放置在L1上的節點的排序，以使弧交叉的數量最小化（同時在L2上的W中的節點的排序是給定和固定的）。問題 的應用程序可以在VLSI佈局和分層結構圖中找到。

但是，雙面和單面問題分別由Garey和Johnson以及Eades和Wormald展示爲NP-hard 。

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

，並得到類似的東西爲免費 :-)：