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