指定した次数列をもつ連結外平面グラフの列挙

摘要

指定された特徴をもつ対象が存在するのか，また存在するとき幾つ存在するのか，そのような対象を抜けなく重複なく列挙する，等は科学的考察の基本である.近年，指定した条件を満たすグラフを高速に列挙するアルゴリズムが多数開発されている.次数列や平面性はグラフの重要な特徴であり多くの研究がある.指定された次数列をもつ単純グラフを1個当り多項式時間で列挙するアルゴリズムが知られている.本研究では，指定された次数列をもつ連結外平面グラフを1個当り多項式時間で列挙するアルゴリズムを設計する.