平面グラフ描画アルゴリズムに関する研究

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

平面グラフGの描画で,各辺が互いに交差しない直線分として描かれ,各面が全て凸多角形で描かれる描画をGの凸描画という.Gの凸描画において,Gの外閉路に対応する多角形を外凸多角形という.平面グラフGが凸描画を持つための必要十分条件は1984年に千葉らによって与えられていた.しかし,Gの凸描画の外凸多角形が何個の頂点を持たねばならないかは知られていなかった.平成16年度の本研究において,外凸多角形が三角形である凸描画を持つための平面グラフGに関する必要十分条件を与えると共に,この結果を学術雑誌に投稿し,採録されていた.平成17年度の本研究において,上記の必要十分条件をより一般化し,Gが凸描画を持つために必要な外凸多角形の頂点の最小個数について解析すると共に,Gの外頂点数最小の凸描画を求める線形時間アルゴリズムを与えた.Gが凸描画を持つために必要な外凸多角形の頂点の最小個数に関する条件を与えたことにより,無駄な外頂点のないGの凸描画を求めることができるため,理論的に極めて重要な結果となる.以上の成果を国内学会,国際学会において発表すると共に,学術雑誌に投稿した.更に凸描画以外の描画法についても研究を行った.平面グラフGの平面描画で,各辺が水平線分あるいは垂直線分で描画され,各内面が長方形であるものをGの内部矩形描画と呼ぶ.本研究では,Gが内部矩形描画を持つための必要十分条件を与えると共に,Gの内部矩形描画を求める多項式時間アルゴリズムを与えた.この成果を学術雑誌に投稿し,採録が決定された.