Planarity の解き方

これって非常に局所性の強いグラフが生成されているので予定調和的に解けていくんだけど、一ヶ所はまるところがあります。



それは「端っこでない点を端に置くと回り込む点が多数出て収集がつかなくなること」。で、3点あるいは2点としか繋がってない点は端っこであることが多いので、それから始めると良いみたい。そこで前線を拡大して行けば良い。なんだけど、それだと「点をどけてスペースを開ける」作業がうざいし、まだ配置してない点と接続線がパーフェクトシャッフルされてしまう。



で、ふっと考えてみると、どっか任意の閉空間をドーナッツの穴と考えると、そのまま裏っ返せるはずだよね。で、裏っ返しに解いて行けば回り込みは存在しない。しかも、隣接する閉空間の大きさはそれほど大きくないことが多いので試行錯誤が少ないはず。しかも、外から内に解くので場所あけの再配置が少なくなるはず。



で、やってみると割とうまくいくみたい。ただ最初に選ぶ長方形によっては点の分布が方よってしまうみたいね。