| 講演名 | 2003/10/20 平面グラフの面の面積を指定した8角形描画 ラハマン モハマッド サイドゥル, 三浦 一之, 西関 隆夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 平面グラフGの直交描画で,各内面が高々8個の角を持つ直交多角形で描かれ,外面の輪郭が長方形で描かれたものを,Gの"8角形描画"と呼ぶ.長方形を垂直あるいは水平にスライスすることを繰り返して得られるグラフは"スライスグラフ"と呼ばれる.特に,水平スライスにより得られる上側の部分長方形あるいは下側の部分長方形がそれ以降は垂直にスライスされることがないとき,"良スライスグラフ"と呼ぶことにする.本論文では任意の良スライスグラフは,各内面が指定された面積を持つように8角形描画できることを示すとともに,そのような描画を求める線形時間アルゴリズムを与える.このような描画はVLSIのフロアプランニングに応用される.また,平面グラフが良スライスグラフであるための十分条件を与えるとともに,その条件を満足する平面グラフに対しスライス道の木構造を求める線形時間アルゴリズムを与える. |
| 抄録(英) | An orthogonal drawing of a plane graph is called an "octagonal drawing" if each inner face is drawn as a rectilinear polygon of at most eight corners and the contour of the outer face is drawn as a rectangle. A "slicing graph" is obtained from a rectangle by repeatedly slicing it vertically and horizontally. A slicing graph is called a "good slicing graph" if either the upper subrectangle or the lower one obtained by any horizontal slice will never be vertically sliced. In this paper we show that any good slicing graph has an octagonal drawing with prescribed face areas, in which the area of each inner face is equal to a prescribed value. Such a drawing has practical applications in VLSI floorplanning. We also give a linear-time algorithm to find such a drawing. We furthermore present a sufficient condition for a plane graph to be a good slicing graph, and give a linear-time algorithm to find a tree-structure of slicing paths for any graph satisfying the condition. |
| キーワード(和) | グラフ描画 / 8角形描画 / 面の面積推定 / アルゴリズム / VLSIフロアプランニング |
| キーワード(英) | Graph Drawing / Octagonal Drawing / Prescribed Face Area / Algorithm / VLSI Floorplanning |
| 資料番号 | COMP2003-45 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2003/10/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 平面グラフの面の面積を指定した8角形描画 |
| サブタイトル（和） | |
| タイトル（英） | Octagonal Drawings of Plane Graphs with Prescribed Face Areas |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ描画 / Graph Drawing |
| キーワード(2)（和/英） | 8角形描画 / Octagonal Drawing |
| キーワード(3)（和/英） | 面の面積推定 / Prescribed Face Area |
| キーワード(4)（和/英） | アルゴリズム / Algorithm |
| キーワード(5)（和/英） | VLSIフロアプランニング / VLSI Floorplanning |
| 第 1 著者 氏名（和/英） | ラハマン モハマッド サイドゥル / Md. Saidur Rahman |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 Guraduate School of Information Sciences, Tohoku University |
| 第 2 著者 氏名（和/英） | 三浦 一之 / Kazuyuki Miura |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 Guraduate School of Information Sciences, Tohoku University |
| 第 3 著者 氏名（和/英） | 西関 隆夫 / Takao Nishizeki |
| 第 3 著者 所属（和/英） | 東北大学大学院情報科学研究科 Guraduate School of Information Sciences, Tohoku University |
| 発表年月日 | 2003/10/20 |
| 資料番号 | COMP2003-45 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 394 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |