| 講演抄録／キーワード |
| 講演名 |
2006-10-17 09:00
平面グラフの矩形外周格子凸描画
○鎌田 彰（東北大）・三浦一之（福島大）・西関隆夫（東北大） |
| 抄録 |
（和） |
平面グラフの凸描画においては，全ての辺は交差しない直線分で描かれ，全ての面は凸多角形で描かれる．
格子凸描画においては，全ての点は整数格子点上に配置しなければならない．
平面グラフ$G$は，内部3連結のとき，かつそのときに限り凸描画を持つ．
また内部3連結平面グラフ$G$が3連結であるか，あるいは$G$の3連結成分分解木$T(G)$に葉が2個あるいは3個しかないならば，$G$は大きさ$n \times n$の整数格子内に格子凸描画できる．
ここで$n$は$G$の点数である．
本文では，内部3連結平面グラフ$G$の分解木$T(G)$に葉がちょうど4個あるならば，$G$を大きさ$2n \times n^2$の整数格子内に格子凸描画できることを示す．
また，そのような描画を線形時間で見つけるアルゴリズムを与える．
既知の格子描画アルゴリズムで得られる描画においては外周は3角形として描画されるのに対し，本文の格子凸描画においては外周は長方形として描画される． |
| （英） |
In a convex drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection and all facial cycles are drawn as convex polygons.
In a convex grid drawing, all vertices are put on grid points.
A plane graph $G$ has a convex drawing if and only if $G$ is internally triconnected,and an internally triconnected plane graph $G$ has a convex grid drawing on an $n \times n$ grid if $G$ is triconnected or the triconnected component decomposition tree $T(G)$ of $G$ has two or three leaves, where $n$ is the number of vertices in $G$.
In this paper, we show that an internally triconnected plane graph $G$ has a convex grid drawing on a $2n \times n^2$ grid if $T(G)$ has exactly four leaves.
We also present an algorithm to find such a drawing in linear time.
Our convex grid drawing has a rectangular contour, while most of the known algorithms produce grid drawings having triangular contours. |
| キーワード |
（和） |
アルゴリズム / 格子凸描画 / グラフ描画 / 平面グラフ / 3連結 / / / |
| （英） |
algorithm / convex grid drawing / graph drawing / plane graph / triconnected / / / |
| 文献情報 |
信学技報, vol. 106, no. 289, COMP2006-31, pp. 1-8, 2006年10月. |
| 資料番号 |
COMP2006-31 |
| 発行日 |
2006-10-10 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|