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

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

平面グラフGの描画で,各点が整数格子の格子点上に配置され,各辺が互いに交差しない直線分として描かれ,各面が全て凸多角形で描かれる描画をGの格子凸描画という.Gの点数をnとしよう.本研究において,内部3連結平面グラフGの分解木に葉がちょうど4個あるならば,Gを大きさ2_n×n^2の整数格子内に格子凸描画できることを証明するとともに,そのような描画を求める線形時間アルゴリズムを与えた.以上の結果を学術雑誌に投稿した.更に凸描画以外の描画法についても研究を行った.平面グラフGの描画で,Gの各点が整数座標を持ち,Gの各辺が互いに交差しない直線分として描かれるものをGの格子直線描画という.Gの格子直線描画で,Gの任意の辺の両端点により定義される軸平行な長方形の内部にGの点が含まれないものをGの矩形勢力描画という.矩形勢力描画で長方形の周上に点の存在を許すものを開矩形勢力描画という,本研究において,任意の平面グラフが開矩形勢力描画を持つための必要十分条件を与えるとともに,Gがその条件を満足するときGを(n-1)×(n-1)の整数格子上に多項式時間で開矩形勢力描画するアルゴリズムを与えた.以上の結果を学術雑誌に投稿した.