平面的グラフの矩形描画

• ラハマン モハマド サイドゥル

  東北大学大学院情報科学研究科

• 西関 隆夫

  東北大学大学院情報科学研究科

• ゴーシュ シュバシシュ

  アルバータ大学

書誌事項

タイトル別名

• Rectangular Drawings of Planar Graphs

抄録

平面的グラフは平面上への埋め込みが固定されておらず,いろいろな埋め込みがありえる.一方,埋め込みが固定された平面的グラフは平面グラフと呼ばれる.平面グラフの矩形描画では,各点は平面上の点として描かれ,各辺は水平あるいは垂直線分として描かれ,各面は矩形として描かれる.平面的グラフの少なくとも1つの平面埋め込みが矩形描画を持つならば,その平面的グラフは矩形描画を持つという.本論文では最大次数が3の平面的グラフGが矩形描画を持つかどうかを判定し,もし持つならばGの矩形描画を求める線形時間アルゴリズムを与える.
A plane graph is a planar graph with a fixed embedding. In a rectangular drawing of a plane graph, each vertex is drawn as a point, each edge is drawn as a horizontal or vertical line segment, and each face is drawn as a rectangle. A planar graph is said to have a rectangular drawing if at least one of its plane embeddings has a rectangular drawing. In this paper we give a linear-time algorithm to examine whether a planar graph G of the maximum degree three has a rectangular drawing or not, and to find a rectangular drawing of G if it exists.

収録刊行物

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

  電子情報通信学会技術研究報告. COMP, コンピュテーション 102 (258), 21-28, 2002-07-29

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

キーワード

• 平面的グラフ
• アルゴリズム
• グラフ描画
• 矩形描画

詳細情報

• CRID: 1572261552296070016
• NII論文ID: 110003494010
• NII書誌ID: AN10013152
• 本文言語コード: en
• データソース種別:
  • CiNii Articles