平面グラフ判定＆描画アルゴリズム

元論文はhttp://hinkali.com/Education/PlanarityTesting.pdf

ここが日本語で説明してくれている http://www.th.cs.meiji.ac.jp/assets/researches/2007/toyota/index.html

アルゴリズム

• グラフをdfsし、訪れた順にidを振っていく。dfs木と後退辺を覚えておく
• 各辺の優先度をとする。つまり両端のidのmin
• 辺を優先度の大きい順に追加していく
• そのときに2連結になるように、頂点を適宜増やしていく
• 新たなループが生成されるとき、externally activeな頂点を外平面に向けるようにflipする(将来的に処理される辺はすべて外平面に来ているはず)
• 最後まで追加できれば描画完了。無理なら平面グラフでない

externally active

優先度の辺を処理している時点で、がexternally activeであるとは、がidがの頂点が属する2連結成分の要素ではなく、かつであることをいう（後者が重要）。

□が頂点vを処理段階でのexternally activeな頂点。

正当性

証明が複雑すぎて追いきれていないが、方針としては

• もしグラフが平面グラフなのに、後退辺を追加できなかったとする
• 後退辺を遮るexternally activeな頂点が存在する
• それらの位置で場合分け
• いずれもをマイナーにもつので平面でない
• 矛盾

みたいな方針