Hopcroft-Tarjanのアルゴリズム

CS

上に挙げたばかりだけど，これね：

大体は理解した．実際に平面グラフを構成して判定するアルゴリズムなので，おかげでPlanarity.netの必勝法も分かったことになる．
しかし，しかしひどく面倒だ... とても人間が手作業でできるものではない．
やはり適当な1点からDFSで点を辿って極大木を作り，そうして得た経路というか部分木をうまいこと配置していけばよいようだ．しかし部分木を選ぶにも，実際には根の方に辺が伸びているものもある訳で，そういうのは先にやるとドン詰まりになるので後回しにする必要がある．そういう判断を重み付けで行うためにDFSを1回，その知識を活用した実際の埋め込み配置にDFSが1回，計2回必要になる．
なお上に挙げたPDFでは「分かりやすくするため」オリジナルにちょっと変更を加えたらしい．