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

平面图绘制算法研究

• 批准号: 16700002
• 负责人: 三浦 一之
• 金额: $ 1.79万
• 依托单位: Fukushima University (2005)Tohoku University (2004)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16700002/
• 关键词: 平面グラフ; 描画; アルゴリズム; 凸描画; 外頂点数最小; 正規分割; リアライザ; Schnyderラベル付け; 順序全域木

平面グラフGの描画で,各辺が互いに交差しない直線分として描かれ,各面が全て凸多角形で描かれる描画をGの凸描画という.Gの凸描画において,Gの外閉路に対応する多角形を外凸多角形という.平面グラフGが凸描画を持つための必要十分条件は1984年に千葉らによって与えられていた.しかし,Gの凸描画の外凸多角形が何個の頂点を持たねばならないかは知られていなかった.平成16年度の本研究において,外凸多角形が三角形である凸描画を持つための平面グラフGに関する必要十分条件を与えると共に,この結果を学術雑誌に投稿し,採録されていた.平成17年度の本研究において,上記の必要十分条件をより一般化し,Gが凸描画を持つために必要な外凸多角形の頂点の最小個数について解析すると共に,Gの外頂点数最小の凸描画を求める線形時間アルゴリズムを与えた.Gが凸描画を持つために必要な外凸多角形の頂点の最小個数に関する条件を与えたことにより,無駄な外頂点のないGの凸描画を求めることができるため,理論的に極めて重要な結果となる.以上の成果を国内学会,国際学会において発表すると共に,学術雑誌に投稿した.更に凸描画以外の描画法についても研究を行った.平面グラフGの平面描画で,各辺が水平線分あるいは垂直線分で描画され,各内面が長方形であるものをGの内部矩形描画と呼ぶ.本研究では,Gが内部矩形描画を持つための必要十分条件を与えると共に,Gの内部矩形描画を求める多項式時間アルゴリズムを与えた.この成果を学術雑誌に投稿し,採録が決定された.

The plane G is drawn, each side intersects with each other, the straight line is drawn, each side is drawn with a convex polygon, G is drawn with a closed loop, G is drawn with a convex polygon. The necessary conditions for plane drawing were established in 1984. G is a convex polygon, and the vertex of G is a convex polygon. In this study, the necessary conditions for convex polygon to be drawn are discussed. In this study, we generalized the necessary conditions for convex drawing, and analyzed the minimum number of vertices of convex polygon. The minimum number of vertices of convex polygon was determined by the time of convex drawing. The convex drawing of G without vertex is very important in theory. The achievements mentioned above are published in the domestic society and international society, and academic contributions are made. More convex drawing method to study. The plane of G is drawn, each side is divided into horizontal lines, each side is divided into vertical lines, each side is rectangular, each side is divided into G and the inner rectangle is drawn. In this paper, we study the necessary conditions for drawing the inner rectangle of G. The results of this research are published in academic journals, and are collected and recorded.

项目成果

Convex drawings of plane graphs of minimum outer apices

最小外顶点平面图凸图

• 发表时间: 2006
• 期刊: International Journal of Foundations of Computer Science Vol.17 No.5
• 作者: K.Miura;M.Azuma;T.Nishizeki
• 通讯作者: T.Nishizeki

Rectangle-of-influence drawing of plane graphs

平面图的影响矩形图

• 发表时间: 2005
• 期刊: Proc.of Information Visualisation 2005, Asia-Pacific Symposium on Information Visualisation(APVIS2005), ACS 45
• 作者: Kazuyuki Miura;Kazuyuki Miura;Kazuyuki Miura
• 通讯作者: Kazuyuki Miura

Canonical decomposition, realizer, Schnyder labeling and orderly spanning trees of plane graphs

平面图的规范分解、实现器、Schnyder 标记和有序生成树

• 发表时间: 2005
• 期刊: International Journal of Foundations of Computer Science Vol.16・No.1
• 作者: K.Miura;M.Azuma;T.Nishizeki
• 通讯作者: T.Nishizeki

Inner rectangular drawings of plane graphs

平面图内矩形图

• 发表时间: 2006
• 期刊: International Journal of Computational Geometry ＆ Applications Vol.16 Nos.2 ＆ 3
• 作者: K.Miura;H.Haga;T.Nishizeki
• 通讯作者: T.Nishizeki

Inner rectangular drawing of plane graphs

平面图内矩形图

• 发表时间: 2004
• 期刊: Proc.of ISAAC 2004, Lect.Notes in Comp.Sci.(Springer-verlag) 3341
• 作者: Kazuyuki Miura;Kazuyuki Miura;Kazuyuki Miura;Kazuyuki Miura;Kazuyuki Miura;Kazuyuki Miura
• 通讯作者: Kazuyuki Miura