A-017
内部3連結グラフの外5角格子凸描画の面積の改良

佐藤　慧・○三浦一之（福島大）

平面グラフGの凸描画においては，全ての辺は交差しない直線分で描かれ，全ての面は凸多角形で描かれる．Gの凸描画で，各点が整数座標を持ち，外面がk角形であるものを外k角格子凸描画という．nをGの点数としよう．Gの3連結成分分解木T(G)の葉の数kが4以下ならば，GはO(n²)の大きさの整数格子内に外k角格子凸描画できることが知られている．しかし，kが5以上のときに，O(n²)の大きさの整数格子内に外k角格子凸描画できるかどうかは知られていない．本論文では，外5角格子凸描画に必要な格子の面積を改良する．即ち，T(G)の葉がちょうど5枚ならば，大きさ20nx16nの整数格子内にGを外5角格子凸描画できることを証明すると共に，そのような描画を求める線形時間アルゴリズムを与える．