抄録
A-018
5連結平面グラフの格子直線描画
5連結平面グラフの格子直線描画
平面グラフGの各点を整数格子の格子点上に配置し，各辺を互いに交差しない直線分として描画したものをGの格子直線描画という．nをGの点数とし，nは3以上としよう．Gが3連結ならば，Gは(n-2)x(n-2)の格子上に格子直線描画できることが知られている．また，Gが4連結ならば，Gは(n/2)x(n/2)の格子上に格子直線描画できることが知られている．グラフの制約をより厳しく5連結にすることで，格子直線描画に必要な整数格子の大きさはさらに小さくなると予想されるが，どの程度小さくなるかは知られていない．
本論文では，5連結内部三角化平面グラフGは高々(n-m-2)x(n/2)の大きさの格子内に格子直線描画できることを示すとともに，そのような描画を求める線形時間アルゴリズムを与える．ここで，mは入力グラフGに対応して決まる変数であり，3 <= m <= n-7である.
本論文では，5連結内部三角化平面グラフGは高々(n-m-2)x(n/2)の大きさの格子内に格子直線描画できることを示すとともに，そのような描画を求める線形時間アルゴリズムを与える．ここで，mは入力グラフGに対応して決まる変数であり，3 <= m <= n-7である.
