自动绘图算法-猫眼课题宝

自动绘图算法

批准号：

01F00236

负责人：

西関隆夫

金额：

$0.83万

依托单位：

Tohoku University

依托单位国家：

日本

项目类别：

Grant-in-Aid for JSPS Fellows

财政年份：

2001

资助国家：

日本

项目状态：

已结题

起止时间：

2001 至 2003

来源：

https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-01F00236/

关键词：

アルゴリズムグラフ描画矩形描画直交描画折れ曲がり

项目摘要

项目成果

西関隆夫的其他基金

相似基金

相关文献

中文摘要

翻译

点击翻译按钮获取中文摘要

英文摘要

本年,我々は平面グラフの"矩形描画"および"直交描画"に関する研究を行った.これらの描画は,回路の設計,VLSIのフロアプラン,建築のフロアプラン,情報の視覚化等,数々の実用的な応用を持っている.平面グラフGの矩形描画とは,Gの各点が平面上の点で描かれ,Gの各辺が水平線分あるいは垂直線分で描かれ,Gの各面の輪郭が矩形で描かれたGの描画のことである.平面的グラフGの少なくとも1つの平面埋め込みが矩形描画を持つとき,Gは矩形描画を持つという.平面的グラフGは,一般には指数個の埋め込みを持つので,最大次数が3である平面的グラフGが矩形描画を持つかどうかを判定する問題は単純ではない.なぜならば,上記の線形時間アルゴリズムをGの全ての埋め込みに対して判定する自明なアルゴリズムは,多項式時間では実行できないからである.本年,我々は最大次数が3の平面的グラフGが矩形描画を持つかどうかを判定し,かつGの矩形描画が存在するとき,Gの矩形描画を求める線形時間アルゴリズムを与えた.平面グラフGの直交描画とは,Gの各点が平面上の点で描かれ,Gの各辺が水平線分あるいは垂直線分の列で描かれたGの描画のことである.辺上で方向が変わる点を折れ曲がりという.直交描画の折れ曲がりの数を最小にすることは興味深い問題である.VLSIのフロアプラン問題では,入力グラフとして,しばしば最大次数が3の平面グラフが用いられるが,そのような平面グラフGは折れ曲がりのない直交描画を持つかもしれないことが知られていた.しかし,平面グラフGが折れ曲がりのない直交描画を持つための単純な必要十分条件は知られていなかった.本年,我々は最大次数が3である平面グラフGが折れ曲がりのない直交描画を持つための必要十分条件を与えた.さらに,Gの折れ曲がりのない直交描画が存在するとき,そのような描画を求める線形時間アルゴリズムを与えた.

期刊论文(2)

专著(0)

科研奖励(0)

会议论文

M.S.RAHAMAN: "Rectangular drawings of Plane Graphs without designated corners"Computational Geometry: Theory and Applications. 21・3. 121-138 (2002)

M.S.RAHAMAN：“无指定角的平面图形的矩形图”计算几何：理论与应用 21・3（2002）。

DOI： --

发表时间：

期刊：

影响因子： --

作者：

[]