平面グラフレイアウト

Question

グラフをレイアウトする際のエッジのオーバーラップ最小化手法は何ですか？ （できればGraphVizに関連することが望ましい）また、平面的にグラフをレイアウトできる既存のソフトウェアはありますか？

現在のレイアウト - http://www.evecakes.com/doodles/master.gif

左上隅のピンクのセクションはきれいに見えますが、ライトブルーセクションには回避可能なエッジオーバーラップがあります。

Answer 1

一般的なグラフの場合、最小エッジの交差点でグラフの平面レイアウトを決定する問題（ 交差番号）NPハードです。したがって、いくつかのヒューリスティックな方法が使用されます（ 力ベースのレイアウト アルゴリズム）。

以下のページでは、GraphVizアルゴリズムを簡単に説明し、それらを使用するためにそれらを使用するいくつかの方法を提案します。また、アルゴリズムに関するより多くの情報を含むはずのPDFへのリンクもあります。

http://rss.acs.unt.edu/rdoc/library/rgraphviz/html/graphvizlayouts.html

それが役立つことを願っています。

Answer 2

次のオープンソースJavaライブラリには、平面グラフのレイアウトに役立つ可能性のあるアルゴリズムがいくつかあります。http://open.trickl.com/trickl-graph/index.html

特に、次のクラスは問題に対する分析ソリューションを提供します。

Chrobakpaynelayout （Aaron WindsorによるブーストC ++実装に基づく）http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html

FoldFreeLayout （センサーネットワークにおけるアンカーフリーの分散型ローカリゼーションに基づく * Nissanka B. Priyantha、Hari Balakrishnan、Erik Demaine、およびSeth Teller）

あなたがやりたいのは、このようなものを、オーバーラップを保証しない最初の「試み」として使用することですが、見た目は良くないかもしれません。その後、フォース指向のアルゴリズムを適用して、ノードをより公平にスペースにします。

残念ながら、ライブラリはリリースされたばかりなので、ドキュメントが不足しています。ただし、理論ではなく実際のコードを提供することで役立つかもしれません。