著者

ラハマン モハマド サイドゥル 西関 隆夫 ゴーシュ シュバシシュ

出版者

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

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.102, no.258, pp.21-28, 2002-07-29

---

平面的グラフは平面上への埋め込みが固定されておらず,いろいろな埋め込みがありえる.一方,埋め込みが固定された平面的グラフは平面グラフと呼ばれる.平面グラフの矩形描画では,各点は平面上の点として描かれ,各辺は水平あるいは垂直線分として描かれ,各面は矩形として描かれる.平面的グラフの少なくとも1つの平面埋め込みが矩形描画を持つならば,その平面的グラフは矩形描画を持つという.本論文では最大次数が3の平面的グラフGが矩形描画を持つかどうかを判定し,もし持つならばGの矩形描画を求める線形時間アルゴリズムを与える.