- 著者
-
ラハマン モハマッド サイドゥル
中野 眞一
西関 隆夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
- 巻号頁・発行日
- vol.98, no.380, pp.1-8, 1998-10-30
平面グラフGを整数格子上に次の(1)-(3)を満たすように描画したものをGの箱-矩形描画という.(1)各点は矩形として描画する.(この矩形を箱と呼ぶ.)(2)各辺は水平もしくは垂直線分として描画する.(3)各面の輪郭は矩形として描画する.平面グラフGの描画で, 各点を格子点として描画し, 各面の輪郭を矩形として描画したものを, Gの矩形描画という.箱-矩形描画は, 通常の矩形描画の自然な一般化である.本論文では, 平面グラフGが箱-矩形描画を持つための必要十分条件を与える.また, Gが箱-矩形描画を持つならば, その描画を求める線形時間アルゴリズムも与える.求められた描画の高さと幅の和は, m+2以下である.ここで, mはGの辺数である.