Outerplanar graph の判定

なんとなく他人の研究の話を聞いていたら,有限無向グラフを入力として,そのグラフが外平面グラフ (Outerplanar Graph) であるか否か判定するアルゴリズムの話が出て来て面白かった.外平面グラフだと計算量が落ちるアルゴリズムがいろいろとあるらしく,グラフアルゴリズム的には興味のある対象であると.なるほど.

んで,なんとなーくわかったことは,もとのグラフから次数が1の頂点をひっこぬき,次に次数が2の頂点をどんどん簡約していって,最終的に特定の形になれば Outerplanar であると判定できるらしい.

詳しいことはよくわからなかったので,今度 (いつ?) ちゃんと論文を読むとするかね.