| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-10-16 10:35 Small Grid Drawings of Planar Graphs with Balanced Bipartition Xiao Zhou・○Takashi Hikino・Takao Nishizeki（Tohoku Univ.）  COMP2009-33 |
|
| 抄録 | （和） | 平面グラフ$G$の格子描画では，$G$の各点は2次元整数格子上に配置され，各辺は直線分として描かれ，どの2辺も共通の端点以外では交差しない．任意の平面グラフ$G$は$(n-2)\times (n-2)$の整数格子上に格子描画を持ち，それは線形時間で求まる．ここで，$n$は$G$の点数である．本文では，平面グラフ$G$がバランスよい二分割を持つならば，$G$は小さな格子描画を持つことを示す．より詳細に言えば，分離点対が$G$を二つの辺素な部分グラフ$G_1$と$G_2$に二分割するならば，$G$は$W\times H$の格子描画を持つ．ここで，幅$W$と高さ$H$はともに$G_1$と$G_2$の点数が多い方の数より小さい．特に，任意の直並列グラフは$(2n/3)\times (2n/3)$の格子描画を持ち，それは線形時間で求まる． |
| （英） | In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straight-line segment without any edge-intersection. It has been known that every planar graph $G$ of $n$ vertices has a grid drawing on an $(n-2)\times (n-2)$ integer grid and such a drawing can be found in linear time. In this paper we show that if a planar graph $G$ has a balanced bipartition then $G$ has a grid drawing with small grid area. More precisely, if a separation pair bipartitions $G$ into two edge-disjoint subgraphs $G_1$ and $G_2$, then $G$ has a grid drawing on a $W\times H$ grid such that both the width $W$ and height $H$ are smaller than the larger number of vertices in $G_1$ and in $G_2$. In particular, we show that every series-parallel graph $G$ has a grid drawing on a $(2n/3)\times (2n/3)$ grid and such a drawing can be found in linear time. | |
| キーワード | （和） | 格子描画 / 直並列グラフ / 平面グラフ / / / / / |
| （英） | grid drawing / series-parallel graph / planar graph / / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 235, COMP2009-33, pp. 9-15, 2009年10月. | |
| 資料番号 | COMP2009-33 | |
| 発行日 | 2009-10-09 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2009-33 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2009-10-16 - 2009-10-16 |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2009-10-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Small Grid Drawings of Planar Graphs with Balanced Bipartition |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 格子描画 / grid drawing |
| キーワード(2)（和/英） | 直並列グラフ / series-parallel graph |
| キーワード(3)（和/英） | 平面グラフ / planar graph |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 周 暁 / Xiao Zhou / シュウ ギョウ |
| 第1著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 引野 高嗣 / Takashi Hikino / ヒキノ タカシ |
| 第2著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 西関 隆夫 / Takao Nishizeki / ニシゼキ タカオ |
| 第3著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 講演者 | 第2著者 |
| 発表日時 | 2009-10-16 10:35:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2009-33 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.235 |
| ページ範囲 | pp.9-15 |
| ページ数 | 7 |
| 発行日 | 2009-10-09 (COMP) |
[研究会発表申込システムのトップページに戻る]