A-021 内部3連結グラフの外5 角格子凸描画(アルゴリズム・コンピュテーション(2),A分野:モデル・アルゴリズム・プログラミング)
スポンサーリンク
概要
- 論文の詳細を見る
平面グラフGの凸描画においては,全ての辺は交差しない直線分で描かれ,全ての面は凸多角形で描かれる.Gの凸描画で,各点が整数座標を持ち,外面がk角形であるものを外k角格子凸描画という.Gが凸描画を持つための必要十分条件は,Gが内部3連結であることである.Gが3連結であるか,あるいはGの3連結成分分解木T(G)の葉の数が3枚以下ならば,T(G)は大きさn×nの整数格子内に外3角格子凸描画でき,T(G)の葉の数がちょうど4 枚ならば大きさ2n×2nの整数格子内に外4角格子凸描画できる.ここでnはGの点数である.本論文では,T(G)の葉が5枚のとき,内部3連結グラフGは6n×n^2の大きさの整数格子内に外5角格子凸描画できることを証明すると共に,そのような描画を求める線形時間アルゴリズムを与える.
- FIT(電子情報通信学会・情報処理学会)運営委員会の論文
- 2011-09-07