グラフをトーラスとか射影平面に描画するアルゴリズムの話

入力として与えられたグラフをsphereとかtorusとか射影平面(N1)にembedできるかどうかを判定し、できるならば具体的に一つembeddingを出力せよという話。nは頂点数。基本的にかなり大雑把な話しかしないので雰囲気だけつかんでくれたらと思う。

K5とK_3,3が平面的グラフの禁止マイナー(obstructionと呼ぶらしい)であるというKuratowskiの定理はあまねく知れ渡っていることであるが、実はTorus上で考えるとこの二つのobstructionはどちらもembeddできることが分かる。ちなみに後で出てくるが、N1描画の時の禁止マイナーなグラフは全部で103種類存在する。

- sphere ... O(n)のアルゴリズムがある。実装されてる。

- N1

   - O(n) ... 複雑すぎて実装むりぽ。

   - O(n^2) ... MR Algorithmと呼ばれるものがある。O(n)を簡単にしたもの。実装済み。

- torus

   - O(n) ... あまりにも複雑。当然実装はされていない。

   - O(n^3) ... JM Algorithmと呼ばれているものがある。めちゃ複雑。実装したよ、ていう人が過去にいたけどそれダウト、って言う人もいる。

   - 2^O(n) ... NM Algorithm 及び Woodcock's Algorithmが有名。Woodcockの方が定数倍的な意味で早いが実装は十分複雑。どちらも実装はされてるぽい(?)

ここに出てきた固有名詞のついてるアルゴリズムはどれも "embedding extension"と呼ばれるアプローチを取っている。

"embedding extension"とは、入力されたグラフGのある部分グラフを"frame"と呼び、基本的には記号Kで表す。まずこれをtorusまたはN1上にframeをembedするところから始まる。

例えばframeとしてはK5やK_3,3と位相同型なグラフを採用することが多い(これらはtorusにもN1上にもembed可能)

このembeddingは定数通りしかないため、それらを全列挙し、各embeddingに対してグラフの残りの部分(K-bridgeと呼ばれる)のembeddingを試してみて、うまくいくものがみつかったらそれを返すというものである。

frameとして簡単なグラフ(例えばただの閉路とか)を採用すれば実装は楽になるが時間計算量は高くなり、複雑なグラフ(K5とか)を採用すれば場合分けがやばいけど時間計算量は落ちる。そこにtrade offの関係がある。

- N1にembedする場合(NM Algorithm)

　frameとしてK5もしくはK_3,3と位相同型なGの部分グラフを採用する。これらのN1上へのembeddingはそれぞれ27、6通りしかない。そして残りの部分を頑張る。

　一般に、曲面にグラフをembedした場合は幾つかの辺で囲まれた面ができる。具体的には、曲面からグラフの線分をハサミで切り取り除いたものを考え、そのそれぞれの連結部分のことを"face"と呼ぶ。

　まずframeを選びN1上にembedしたら幾つかのfaceができ、残りの部分(K-bridge)をどのfaceにembedすれば良いか、という問題が生じてくる。しかし、基本的にK-bridgeを埋め込むことができるようなfaceは高々3通りしかなく、しかも3通りのfaceがあるようなbridgeは定数個しかないことが知られている。そして残りのbridgeについては高々2通りしかなく、その割り当ては2-SATで解ける。そこでこの定数個の3通りの割り当てを全列挙し、それぞれの場合に対して2-SATのインスタンスを生成し、解けば良い。この2-SATはclauseがO(n^2)個あるので、全体としてこの2-SATはO(n^2)で解けるのでNM-AlgorithmはO(n^2)で出来てしまう。

- Torusにembedする場合(NM Algorithm , Woodcock Algorithm)

　NM Algorithmはframeとして閉路を採用する。 グラフの中にK5またはK_3,3と位相同型な部分グラフを見つけこれをKとする。さらにKの中から部分グラフK'をとる。(KがK5ならK'はK4, KがK_3,3ならK'はK_2,3)とする。 このK'には実は"ある良い性質"を持った閉路が必ず一つ以上存在することが分かっていて、その「良い性質を持った閉路」をframeとして採用する。直感的に言うとトーラスの筒のところを一周させるようにframeをembedする。もしグラフがTorus上embeddableならばこのようにして列挙した閉路で探索していくと必ずうまくいくものが見つかるということが保証されている。続きの話を直感的に説明すると、この閉路によってトーラスを切り、筒状の立体を得る。そして残りの部分をこの筒状のfaceに頑張ってembedする。

　しかしN1では各faceに対してその境界を見てみると同じ頂点が2回現れることがない。しかしTorusでは2回現れることがありうる。この違いによってbridgeをfaceに割り当てた後でもembedの仕方が何通りか存在してしまい、計算量が膨れてしまう。ここにN1とTorusの大きな違いがある。

　Woodcock AlgorithmはframeとしてK_5またはK_3,3と位相同型な部分グラフを採用する。embedの仕方とかも全通り列挙してあとはNM Algorithmと同じようなことをやる。

　JM法は理論的には多項式時間O(n^3)で解けるアルゴリズムである。これは、冒頭で言った103種類のobstructionと位相同型なグラフをframeとして採用するらしい。そしてembeddingを全通り試して上手いことやるとO(n^3)で解けるらしいが定数倍などもかなりヤバイらしい。

ちょっと詳細を省きすぎてしまった感があってアレなのでそのうちグラフのembeddingの基本的な事柄について丁寧な記事を書きたい。ところで平面性判定や平面embeddingがO(n)でできるという事実に驚いた。