| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 6A |
| セッション名 |
| グラフ・ネットワーク |
| 講演日 |
| 2009/09/04 |
| 講演場所(会議室等) |
| A会場（9号館1F 911教室） |
| 講演番号 |
| A-026 |
| タイトル |
| グラフ分割を用いた格子描画法 |
| 著者名 |
| 引野 高嗣, 周 暁, 西関 隆夫, |
| キーワード |
| 格子描画, 平面的グラフ, グラフ分割, 直並列グラフ |
| 抄録 |
|
平面グラフ<l>G</l>の格子描画では,<l>G</l>の各点を2次元整数格子上に配置し,各辺が直線分として描かれ,どの2辺も共通の端点以外では交差しない. 格子描画の面積とは,描画全体を囲む最小の軸平行な長方形の面積である. 格子描画の幅<l>W</l>と高さ<l>H</l>は,各々その長方形の幅と高さである. 平面グラフ<l>G</l>の格子描画を求める線形時間アルゴリズムとして,Realizer法,シフト法が知られている. 前者の描画では幅<l>W</l>と高さ<l>H</l>が<l>n</l>-2であり,後者では<l>W</l>=<l>n</l>-1,<l>H</l>=<l>n</l>-2である. ここで,<l>n</l>は<l>G</l>の点数である. 本論文では,直並列グラフは<l>W</l>=2<l>n</l>/3+1,<l>H</l>=2<l>n</l>/3-1なるように格子描画できることを示すとともに,そのような描画を求める線形時間アルゴリズムを与える. |
| 本文pdf |
| PDF download (157.9KB) |