| 講演抄録／キーワード |
| 講演名 |
2005-10-18 15:55
Convex Drawings of Plane Graphs of Minimum Outer Apices
○Kazuyuki Miura（Fukushima Univ.）・Machiko Azuma・Takao Nishizeki（Tohoku Univ.） |
| 抄録 |
（和） |
平面グラフ$G$の凸描画では，
$G$の全ての面閉路は凸多角形で描かれる．
外閉路に対応する多角形を外凸多角形という．
平面グラフ$G$が凸描画を持つための必要十分条件は知られていた．
しかし，
$G$の凸描画の外凸多角形が何個の頂点を持たねばならないかは知られていなかった．
本論文では
$G$が凸描画を持つために必要な
外凸多角形の頂点の最小個数は，
$G$から新しく構成されるグラフの3連結成分分解木の葉の個数に等しいことを示すと共に，
$G$の外頂点数最小の凸描画が線形時間で求まることを示す． |
| （英） |
In a convex drawing of a plane graph $G$,
every facial cycle of $G$ is drawn as a convex polygon.
A polygon for the outer facial cycle is called
an outer convex polygon.
A necessary and sufficient condition for a plane graph $G$
to have a convex drawing is known.
However,
it has not been known how many apices of an outer convex polygon
are necessary for $G$ to have a convex drawing.
In this paper,
we show that the minimum number of apices of an outer convex polygon
necessary for $G$ to have a convex drawing is,
in effect,
equal to the number of leaves in a triconnected component decomposition
tree of a new graph constructed from $G$,
and that a convex drawing of $G$
having the minimum number of apices can be found in linear time. |
| キーワード |
（和） |
グラフ描画 / 凸描画 / 外頂点数最小 / / / / / |
| （英） |
Graph Drawing / Convex Drawing / Minimum Outer Apices / / / / / |
| 文献情報 |
信学技報, vol. 105, no. 343, COMP2005-42, pp. 45-51, 2005年10月. |
| 資料番号 |
COMP2005-42 |
| 発行日 |
2005-10-11 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|