二部グラフにおける交差数を最小化

Question

次のアルゴリズムの問​​題は、私に起こりました図のように列に表示されます。エッジ交差の数が最小になるように、各列内のノードをどのように再配置できますか？私はこの問題が一般的なグラフ（link）のNP困難であることを知っていますが、グラフが二者であると考えると、いくつかのトリックがありますか？フォローアップとして

、唯一Vにエッジを有する第3列ワット、何がありますか？それとも？

Answer 1

Gareyと Johnsonの交差数の原稿用紙は、エッジ交差 の数を最小限にする二部グラフのNP困難であることを証明したことに言及 On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi紙。二部グラフを考えると

、2層構造の描画は、第1ノード集合V上のノード を置くことで構成されています。実際には、それはあなたが1列に最適な順序を言われても、まだNP困難 です直線L1とし、第2節点集合Wに平行線L2上に節点を置く。 2層の図面における円弧間の交差数を最小化する問題は、最初にHararyとSchwenkによって導入された でした。片側交差最小化 問題は、L1の上に置かれるべきV内のノードの順序を見つけるように要求するので、アーク横断の数は最小限に抑えられる（ の順序が与えられ、固定される）。 の問題のアプリケーションは、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

と無料 :-)のためにそのような何かを得る：