抄録

○三浦一之（福島大）

平面グラフGの凸描画においては，全ての辺は交差しない直線分で描かれ，全ての面は凸多角形で描かれる．Gの凸描画で，各点が整数座標を持ち，外面がk角形であるものを外k角格子凸描画という．nをGの点数としよう．Gの3連結成分分解木T(G)の葉の数kが6以下ならば，Gはnの多項式の大きさの整数格子内に外k角格子凸描画できることが知られている．
本論文では，T(G)の葉が7枚のとき，内部3連結グラフGがある条件を満足するならば，Gは6n×2n²の大きさの整数格子内に外7角格子凸描画できることを証明すると共に，そのような描画を求める線形時間アルゴリズムを与える．