抄録
A-021
内部3連結グラフの外5角格子凸描画
○三浦一之（福島大）
平面グラフGの凸描画においては，全ての辺は交差しない直線分で描かれ，全ての面は凸多角形で描かれる．Gの凸描画で，各点が整数座標を持ち，外面がk角形であるものを外k角格子凸描画という．Gが3連結であるか，あるいはGの3連結成分分解木T(G)の葉の数が3枚以下ならば，Gは大きさn x nの整数格子内に外3角格子凸描画でき，T(G)の葉の数がちょうど4枚ならば大きさ2n x 2nの整数格子内に外4角格子凸描画できる． ここで，nはGの点数である． 本論文では，T(G)の葉が5枚のとき，内部3連結グラフGは6n x n2の大きさの整数格子内に外5角格子凸描画できることを証明すると共に，そのような描画を求める線形時間アルゴリズムを与える．