平面判定アルゴリズム
平面判定は $ \Omicron(|V|) でできることが知られている
アルゴリズム
プリプロセス
1. 行きがけ順に頂点 ID を振る
2. DFS 木と後退辺を覚えておく
2. 各辺の優先度を $ \min(u,v) とする。(両端 ID の min)
DFS の際に訪れた頂点を端点に持つ辺を全て (適当な順序で) スタックに移動させ (元のグラフからは削除)、スタックの一番上に乗った辺を通って次の頂点を訪問すれば良い。
後で辺を描画するときにスタックの辺を上から取っていけば良い
描画
以下を繰り返す
1. 辺を優先度の大きい順に描画領域に追加する
同じ優先度の場合は DFS 木に含まれる辺を優先
辺と一緒に適宜頂点を追加
2. 新たなループが生成されるとき externally active な頂点を外平面に向けるようにする
externally active: その頂点 / その子孫から後退辺を辿って、今見ている優先度よりも小さいIDの頂点に行ける点 (まだ描画が完了していない点)
まだ全ての辺を描画しきっていない頂点
3. 最後まで辺を追加できれば描画完了。無理なら平面グラフではない。
https://scrapbox.io/files/649fa4f7d7fba4001bb63d78.png
https://scrapbox.io/files/649fa4dcd86ea1001b37b7df.png
https://scrapbox.io/files/649fa573590444001cb568d8.png
https://scrapbox.io/files/649fa5c883bec2001beedac4.png
https://scrapbox.io/files/649fa5fe8f7379001bed95ad.png
https://scrapbox.io/files/649fa6f837daa5001ba158e4.png
ループが生成されるとき, 今後辺が追加される点は外周にある (集中線で表している)
https://scrapbox.io/files/649fa78f2ad567001cd68cbe.png
https://scrapbox.io/files/649fa837eabed0001c0534b6.png
ここで詰む
水ー青をそのまま追加すると緑がまだ描画していない辺を持つのに内側にある
緑を外側に移動させて水ー青を引くと、青がまだ描画していない辺を持つのに内側にある
スタックから吐き出した順にノードを並べて左右どちらかに辺を追加していくことで実装できる
実際に描画せずとも、辺を左側に置くか右側に置くかだけをメモリに保存しておけば良い
各頂点に対して左右領域での囲まれ状態を保存し、追加しようとした辺の端点が右で囲まれていれば左に辺を追加しようと試み、左も囲まれていれば終了すればよい?
https://scrapbox.io/files/649fafffd551c6001cc4eb3c.png
ダメ
反例
https://scrapbox.io/files/649fb5ae4e1fc4001cc393a2.png
これから追加しようとする辺$ E_{u,v}に囲まれる頂点は$ u\lt\mathrm{id}\lt{v}を満たす頂点
なので、それらの頂点を調べて externally active かどうか調べて、externally active な頂点が左右両方から囲まれないようにする
反例
DFSの順序をミスった段階で描画不可能になる
https://scrapbox.io/files/649fbbefe55c0d001c61d023.png