グラフの平面化のための最速アルゴリズム

Question

私は複雑なデータとプロセスのためのナビゲーションシステムを開発するためにProcessingを使用しています。その一環として私はかなり深くグラフのレイアウトに入っています。それはすべて楽しく、レイアウトアルゴリズムに関する私の意見は次のとおりです。力指向は賢者のためのものです（ちょうどそれを見てください...笑）、固有ベクトルの投影はクールです、杉山のレイヤーはよく見えますが、グラフのグラフでは失敗します。これまでのところ、データのポイントまで実際に到達するには、エッジ交差を最小限に抑える必要があります。私はNP完全などが

私はXYボクシングを適用すると、行と列間のエッジの交差を減らすために杉山のような順列を使用してからいくつかの良い成功を持っていることを追加する必要があります知っている、知っています。 Viz：グラフ（| V | = 90、平均ログ| V |）は、交差を減らすために行と列の順列を交互に変えることで、11000回の交差→1500回（ボックス化された固有ベクトルによる）→300回となります。

しかし、このマークの周りに何があっても、その結果は明らかではありません。最大の平面部分グラフ 1.A.を作るために

1. 使用BFSか何か：点灯への私の研究は、私は本当に彼らがVLSIのために使うのですかどのような平坦化アルゴリズムを使用することを私に示唆しますレイアウト素敵-よう
2. 巧み最速平坦化アルゴリズムにお考えに返信してください、あなたは任意の特定の最適化に関するいくつかの深さに行くことが歓迎されている元のグラフ

を回復するために、優れたエッジを追加し、平面部分グラフあなたは親しみを持っていました。

ありがとうございます！

Answer 1

すべてのグラフが平面ではない（あなたが知っている）と仮定すると、「常に最良の答えが得られる」アプローチではなく、「次善の」アプローチをとる方が良いかもしれません。

私はこれを言っています。グラウンドスクールの私のルームメイトが同じ問題を抱えていたからです。彼はグラフを平面形式に変換しようとしていましたが、最小限のエッジ交差を保証するすべてのアルゴリズムは遅すぎました。彼は無作為アルゴリズムを実装するだけで何をしたのか。基本的に、グラフをレイアウトしてから、多くの交差点を持つエッジを持つノードをジグザグにして、最終的には最悪のエッジの塊を処理します。

利点は次のとおりです。特定の時間が経過した後に切り取ることができるため、時間が限られている場合は常に一定の時間がかかります。厄介なグラフが表示された場合は、 （すでにレイアウトされたグラフの上に）何か良いものを得るために、コード化するのは比較的簡単です。

交差点で大域的な最小値が得られるとは限りませんが、グラフが高い交差点にぶつかってしまうと、アルゴリズムによってノードの距離が離れて解決されることがあります。本当に奇妙な探しているグラフ。

Answer 2

あなたは既にたくさんのグラフレイアウトを知っていますが、私はあなたの質問がまだ残念ながら不十分であると信じています。

あなたは次の操作を行って、本当にすぐに任意のグラフを平坦化することができます：（1）ランダムに平面上にグラフをレイアウト（2）ここで、クロスは、（3）これは何である（交差で擬似頂点を作成するエッジ計算とにかく、非平面グラフに平面性ベースのレイアウトを使用する場合）（4）新しい頂点と分割エッジで拡張されたグラフは自動的に平面になります。

最初の問題は、エッジ交差の数を最小限に抑えるコンビナトリアル埋め込みを計算するアルゴリズムを持つことにあります。第2の難点は、視覚的に魅力的であるユークリッド平面内のレイアウトを行うためにその組合せ埋め込みを使用することである。直交グラフのレイアウトでは、折れ曲がりの数を最小限に抑え、面のサイズを最大にし、グラフ全体の面積を最小限にするなど、これらの目標は互いに競合する可能性があります。