凸多角形の flip graph

今日は、凸多角形の flip graph の描画についてです。描画ツールは cytoscape を使いました。cytoscape で読める形式に出力するために、igraph を使用しました。igraph は、様々なグラフの性質（直径とか）を調べられるし、いろいろ楽しめそうなので使ってみました。cytoscape は、グラフを頂点とするグラフみたいなのも描画できそうなので、頂点に三角形分割が描けると良いなと思って使いました。まだ、できてませんけど。

下の画像は、6角形から11角形の flip graph です。7 角形くらいから、もう訳が分かりません。

12角形はトポロジ情報は出力できたのですが、描画ツールで読み込めてません。頂点数が１万個を超えているので、多分 Java のメモリ制限を増やせば、いけるんじゃないかなって思います。13角形以降は計算中です。ちゃんとプロファイルしないといけないのですが、多分、二頂点間に辺を付与するかどうかの確認でO(n^2)回やっちゃってるのが、いけないじゃないかなって思います。初歩的な回避策として、n 角形の次数は n - 3 なのでカウンタ用意して枝刈りしようと思います。どこまで n を増やせるのか、ちょっとずつ改善できたらなって思います。

今日は、ちょっと思い立って、描いてみました。基本となる手続きの保証ができた記念に記事にしてみました。