平面的なグラフ

• ZDDとSimPathをやってみた(こちら)
• ZDDは「平面的なグラフ」で特に効果があるそうだ
• これは、いかにもそんな印象もあるけれど、その背景って…?
• 『平面分離定理』
  • 頂点数nの平面(に描ける)グラフは、３つの頂点集合に分けることができて、その分け方ではフロンティアとその左右とに分かれる。フロンティアの左右の頂点集合間にエッジはなく、このようなときに、フロンティアに当たる頂点集合の頂点数は、$2\sqrt{2n}$ 以下である』takano_poster.pdf
• このことから、フロンティアを使うSimPathでは、平面グラフであるなら、処理単位数を大きくしすぎないでできることがわかっている、と、こういうことだった
  • ちなみにフロンティアってこんな感じ(こちら)