抄録
A-004
内部三角化平面グラフの開矩形勢力描画アルゴリズム
○三浦一之(福島大)
平面グラフGの描画で,Gの全ての点が整数格子点上に置かれ,Gの各辺が交差のない直線分で描かれるものをGの格子直線描画と呼ぶ.本論文では,格子直線描画に更なる制約を加えた”開矩形勢力描画”を扱う.Gの格子直線描画における各辺eに対して,eを対角線とする軸平行な長方形の内部をeの開矩形勢力と呼ぶ.Gの格子直線描画で,任意の辺の開矩形勢力内に点が存在しない描画をGの開矩形勢力描画と呼ぶ.内部三角化平面グラフGが開矩形勢力描画を持つための十分条件は知られていたが,必要十分条件は知られていない.
本論文では,内部三角化平面グラフGが開矩形勢力描画を持つための十分条件を改良するとともに,条件を満足するGの開矩形勢力描画を求めるアルゴリズムを与える.