平面グラフかどうかの判定

CS

Planarity.net のゲームは自動でランダムにグラフを生成しているようだが，「たまに解けない問題を出してしまうバグが残っています．御容赦ください」とあった．Wikipediaによれば，あるグラフが平面グラフになる必要十分条件は「そのグラフの部分グラフのうちに，K5 （いわゆる五亡星）または K3,3 の拡大になっているものがあるかどうか」だと言う（Kuratowskiの定理）．

Kuratowskiの定理からは判定を効率よく実行する方法はさっぱり見えてこない．また，それなりに手間をかけて作ってあるPlanarity.netが完璧な判定を実装してないということは，まともな効率のアルゴリズムが知られていないということだろうか？ なんかHopcroft-Tarjanってのが線形らしいんだが... ついでに，そもそもランダム生成の段階で平面グラフであることを保証する生成アルゴリズムもあるようだ．まぁ「実装が面倒」ってのはアリだよな（笑

ただグラフ理論は難しそうなのでハマりこむことは避けたい．上定理も，理解するにはかなりの準備が必要になりそうだ．

追記： Kuratowskiの定理というのは，Robertson–Seymourの定理の特殊な場合に含まれるらしい．色々な性質が「○○なグラフをマイナー（拡大の逆）として持たないこと」という形に書けるのだとか．生まれ変わって数学の得意な男の子になったら，ちょっとくらい勉強してみたいかも．
追記2： Planarity.netでは解きやすいように各頂点の次数（生えている辺の数）に制限を課した上でグラフを生成していると思われるが，そんな制限を考慮した論文なんてないだろうから，そこは差っ引いて考えなきゃいけないな．