A-003
3連結cubic平面グラフの最少線分格子凸描画

○三浦一之（福島大）

平面グラフGの凸描画においては，全ての辺は交差しない直線分で描かれ，全ての面は凸多角形で描かれる．Gの凸描画で，各点が整数座標を持つものを格子凸描画という．Gの凸描画で，極大線分の数が最少となるものを最少線分凸描画という．Gの最少線分凸描画で，各頂点が整数格子上にあるものを最少線分格子凸描画という．Gが3連結cubicグラフならば，Gは最小線分凸描画を持つことが知られている．更に，Gが3連結cubicグラフならば，Gは大きさ(n/2+1)x(n/2+1)の整数格子内に，極大線分の数が下限より高々1本多い格子凸描画を持つことが知られている．ここで，nはGの点数を表す．

本論文では，Gが3連結cubicグラフならば，Gは大きさ(3n/2+1)x(5n/2+1)の整数格子内に最少線分格子凸描画できることを証明するとともに，そのような描画を求める線形時間アルゴリズムを与える．