A-018
平面グラフのトラック描画可能性判定問題の計算複雑度について

◎中島洸夢・宮田洋行・中野眞一（群馬大）

グラフの描画には⼤きな任意性があり，様々な描画について研究が盛んになされている．本研究では，頂点を平⾏な直線上に配置する描画として知られるトラック描画に着⽬する．グラフがトラック描画可能か判定する問題は，関連する描画であるレベル描画の既存研究を詳しく検討するとNP困難であることが容易にわかるが，本研究ではさらに詳しく解析する．具体的には，各内⾯の周⻑がk以下に制限された平⾯埋め込みを持つ平⾯的グラフについて，埋め込みのいずれかがトラック描画可能であるかを判定する問題を考えた．本研究では，k≧10のとき，その問題はNP困難であり，k=3のとき，その問題は多項式時間で解けることを⽰す．