planar-graph

8熱

2答えて

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

5熱

2答えて

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

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

0熱

1答えて

Graphvizで小さな平面グラフを描く

Graphvizでsmall planar graphを描きましたが、1つの場所に2つのエッジの交点があります。私はすべての平面グラフが交差点なしで描かれるわけではないということを読みました。なぜなら、それはNP困難な問題であるからです。また、Graphvizには複雑なアルゴリズムを実装していないこともあります。しかし、その交差点は可能な限り簡単に修正できるので、おそらくそれを取り除く方法がありま

0熱

2答えて

重み付け無向グラフ分割

頂点重みW（V）、E（G）と2つのノードsおよびtを埋め込んだ固定平面の無向循環平面グラフG（V、E）が与えられた場合、GそれをS（G）にsを、T（G）にtをとった2つの連結成分S（G）とT（G）に分割する。頂点sとtは両方とも埋め込みE（G）の外面に属する。私はパーティションのバランスが取れていることを望んでいます。頂点の重みの総和がほぼ同じである必要があります。いいアルゴリズムのアイデアを

7熱

1答えて

グラフのクロスエッジを最小化する

私のプロジェクトの1つにnetworkx（pythonグラフ描画パッケージ）http://networkx.lanl.gov/index.htmlを使用しています。 networkxはかなりクールですが、表示機能の種類はクロスエッジの数に起因しています。グラフのクロスエッジを最小限に抑える方法はありますか？私は交差エッジが最小化されるような方法でノードをソートできるアルゴリズムを意味しますか？

0熱

1答えて

C＃での平面埋め込み（平面顔トラバーサル）アルゴリズム

私はグラフGを持っています。グラフはplanar graphです。グラフのすべての面を探したいと思います。私はconstructing a planar embedding is the way to find the faces (or regions, or cycles)を理解しているので、すべての辺を最大で2つの面で共有する必要があります。 C＃で平面埋め込みアルゴリズムを簡単に実装でき

7熱

1答えて

一般的にNP-hardであるが、平面グラフで多項式時間解を持つ問題のリスト？

グラフの問題として定式化できる多くの問題に遭遇しました。一般的にはNP困難ですが、グラフが平面であることが判明することがあります。したがって、私はこれらの問題とアルゴリズムを学ぶことに興味があります。私が知っている限りでは：平面グラフフォー着色立方平面グラフの平面グラフ最大独立集合にホープ誰かで最大カットこのリストを完成することができます。 NP完全問題のこのcompendiumで

2熱

2答えて

グラフ構造の直線的な平面埋め込み

これは私の問題です：私は平面であることを知っている（すなわち、エッジが交差していないグラフの埋め込みが存在する）グラフ構造を持っています。私は自分のグラフを取り、それを直線で平面に埋め込むアルゴリズムを必要とします。アルゴリズムはあまり効率的である必要はありません（O（N^2）アルゴリズムはうまくいくでしょう）。任意のアイデア/提案？