Efficient generation algorithms for geometric graph classes

点击翻译按钮获取中文摘要

本研究は幾何的特徴を持つ様々なグラフクラスに対して，ラベル付きおよびラベルなしのグラフを列挙するアルゴリズムを開発し，それらのアルゴリズムの高速化を行っている．2022年度は主に幾何的な特徴を持つグラフに対するグラフ同型性を考慮したグラフ列挙アルゴリズムと多面体の辺展開図の列挙アルゴリズムの開発を行った．グラフ同型性を考慮した幾何的な特徴を持つグラフに対する効率的な列挙アルゴリズムの開発を行った．具体的には真区間グラフ，二部置換グラフ，補鎖グラフ，鎖グラフに対して，ZDD を用いて多項式時間のアルゴリズムを開発している．ZDD とは集合族を圧縮するデータ構造で，膨大な数のグラフ構造を高圧縮で表現することに成功した．これらのグラフクラスのうち，真区間グラフと二部置換グラフは 2n ビットでの対応の取れた文字列として，また補鎖グラフと鎖グラフは n ビットの文字列で表現することができる．これらの文字列とグラフは１対１に対応せず，対称性を考慮する必要がある．対称性をうまく扱うことにより，頂点数 n に対して，n の多項式時間で効率的に列挙可能であることを示した．３次元の多面体を辺に沿って切り開いて２次元上に埋め込む展開図を考える．多面体の展開図は折り紙の基本的な構造として数学や工学などの分野で研究が進められており，代表的なものとして立方体には辺に沿って切り開くと11種類があり，それらは重なりを持たない．しかし，特定の多面体の切り開き方によっては展開図に重なりがある場合がある．これまでいくつかのアルキメデスの立体において重なりを持つ辺展開図が存在する/存在しない，ことが示されていた．本研究では，多面体に対する辺展開図を求めるアルゴリズムを開発し，それを応用することにより，すべてのアルキメデスの立体を含む整面凸多面体すべてにおいて，重なりを持つ辺展開の有無を示すことに成功した．