著者

ラハマン モハマッド サイドゥル 中野 眞一 西関 隆夫

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. 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の辺数である.