講演抄録/キーワード |
講演名 |
2004-10-14 10:30
平面グラフの内部矩形描画 ○三浦一之・芳賀大樹・西関隆夫(東北大) |
抄録 |
(和) |
平面グラフ$G$の各内面が長方形になるように各辺を水平線分あるいは
垂直線分で描くことを,$G$の内部矩形描画と呼ぶ.
本論文では$G$が内部矩形描画$D$を持つための必要十分条件は$G$から新しく作られた
二部グラフが完全マッチングを持つことであることを示す.
また,点数$n$の平面グラフ$G$とその外面の概形が与えられたとき,
即ち外面上の全ての点が凸頂点であるか凹頂点であるかが指定されているとき,
$D$は$O(n^{1.5}/\log n)$時間で求めることができることを示す. |
(英) |
A drawing of a plane graph is called an inner rectangular drawing if every edge is drawn as a horizontal or vertical line segment so that
every inner face is a rectangle. In this paper we show that a plane graph {\it G} has an inner rectangular drawing {\it D} if and only if a new bipartite graph constructed from {\it G} has
a perfect matching. We also show that {\it D} can be found in time $O(n^{1.5}/\log n)$ if {\it G} has {\it n}
vertices and a sketch of the outer face is prescribed,
that is, all the convex outer vertices and concave ones are prescribed. |
キーワード |
(和) |
グラフ描画 / 矩形描画 / 内部矩形描画 / アルゴリズム / / / / |
(英) |
Graph Drawing / Rectangular Drawing / Inner Rectangular Drawing / Algorithm / / / / |
文献情報 |
信学技報, vol. 104, no. 338, COMP2004-35, pp. 1-8, 2004年10月. |
資料番号 |
COMP2004-35 |
発行日 |
2004-10-07 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|