4連結平面グラフの格子凸描画

• 三浦 一之

  東北大学大学院情報科学研究科システム情報科学専攻

• 中野 眞一

  東北大学大学院情報科学研究科システム情報科学専攻

• 西関 隆夫

  東北大学大学院情報科学研究科システム情報科学専攻

書誌事項

タイトル別名

• Convex Grid Drawings of Four-Connected Plane Graphs

抄録

平面グラフの各点を整数格子点上に配置し, 各辺が互いに交わることのない直線分となり, 各内面が凸多角形となるように描画したい. このような描画を格子凸描画という. さらに使用する格子の面積を最小にしたい. 外周上に4つ以上の点を持つ4連結平面グラフは, W+H≤nであるようなW×Hの大きさの整数格子に線形時間で格子凸描画できることを本論文は証明する. ここでnはグラフの点数である. 少なくとも (n/2-1)×(n/2-1) の大きさの整数格子を格子凸描画に必要とするグラフが存在するが, 我々のアルゴリズムは高々⌈n/2⌉×⌊n/2⌋の面積の整数格子内にグラフを格子凸描画するので, 本論文の整数格子の面積に関する結果はほぼ最適である.

収録刊行物

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

  電子情報通信学会技術研究報告. COMP, コンピュテーション 97 (356), 1-8, 1997-10-31

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

キーワード

• グラフ
• 描画
• アルゴリズム

詳細情報

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