权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

平面グラフの凸描画アルゴリズムに関する研究

平面图凸图绘制算法研究

基本信息

批准号：
18700003
负责人：
三浦一之
金额：
$ 1.92万
依托单位：
Fukushima University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2006
资助国家：
日本
起止时间：
2006 至 2007
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18700003/
关键词：
平面グラフ描画アルゴリズム凸描画矩形勢力描画

项目摘要

平面グラフGの描画で,各点が整数格子の格子点上に配置され,各辺が互いに交差しない直線分として描かれ,各面が全て凸多角形で描かれる描画をGの格子凸描画という.Gの点数をnとしよう.本研究において,内部3連結平面グラフGの分解木に葉がちょうど4個あるならば,Gを大きさ2_n×n^2の整数格子内に格子凸描画できることを証明するとともに,そのような描画を求める線形時間アルゴリズムを与えた.以上の結果を学術雑誌に投稿した.更に凸描画以外の描画法についても研究を行った.平面グラフGの描画で,Gの各点が整数座標を持ち,Gの各辺が互いに交差しない直線分として描かれるものをGの格子直線描画という.Gの格子直線描画で,Gの任意の辺の両端点により定義される軸平行な長方形の内部にGの点が含まれないものをGの矩形勢力描画という.矩形勢力描画で長方形の周上に点の存在を許すものを開矩形勢力描画という,本研究において,任意の平面グラフが開矩形勢力描画を持つための必要十分条件を与えるとともに,Gがその条件を満足するときGを(n-1)×(n-1)の整数格子上に多項式時間で開矩形勢力描画するアルゴリズムを与えた.以上の結果を学術雑誌に投稿した.

The plane G is drawn, each point is arranged on the lattice point of the integer lattice, each side is intersected by a straight line, each surface is completely convex polygon is drawn, G is grid convex drawing, G is number of points n. In this study, the inner 3-link plane G is decomposed into 4 leaves,G is large and 2_n×n^2, and the lattice convex drawing is proved. The above results are academic contributions. More convex drawing method to study. The plane G is drawn, the points of G are integer coordinates, the edges of G intersect each other, straight lines are drawn, the edges of G are grid straight lines drawn. The grid straight lines of G are drawn, the edges of G are arbitrary, the ends of G are defined, the axes are parallel, the inner edges of G are points of G, and the rectangular forces of G are drawn. In this study, the necessary conditions for drawing an open rectangle force on an arbitrary plane are set to be sufficient for G (n-1)×(n-1) on an integer lattice with polynomial time for drawing an open rectangle force. The above results are academic contributions.