A study of convex grid drawing algorithms of plane graphs with contours of k-gon

k边形平面图凸网格绘制算法研究

• 批准号: 23700008
• 负责人: MIURA Kazuyuki
• 金额: $ 2.41万
• 依托单位: Fukushima University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23700008/
• 关键词: アルゴリズム; 平面グラフ; 格子凸描画

In a convex drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection and all facial cycles are drawn as convex polygons. In a convex grid drawing, all vertices are put on grid points.In this study, we first show that an internally triconnected plane graph G has a convex grid drawing on a 2n x 2n grid if the triconnected component decomposition tree T(G) has exactly four leaves. We also present an algorithm to find such a drawing in linear time. We then show that an internally triconnected plane graph G has a convex grid drawing on a 6n x n2 grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. Furthermore, We show that an internally triconnected plane graph G has a convex grid drawing on a 6n x n2 grid if T(G) has exactly six leaves. We also present an algorithm to find such a drawing in linear time.

在平面图形的凸图中，所有的边都绘制为没有任何边交的直线段，所有的面循环都绘制为凸多边形。在凸网格绘图中，所有顶点都放在网格点上。在本研究中，我们首先证明，如果三连通成分分解树T(G)恰好有四个叶子，则内部三连通平面图G在2n x 2n网格上绘制凸网格。我们还提出了一种在线性时间内找到这样的图的算法。然后，我们证明，如果T(G)恰好有五个叶子，则内部三连通的平面图G在6n x n2网格上绘制凸网格。我们还提出了一种在线性时间内找到这样的图的算法。此外，我们证明，如果T(G)恰好有六个叶子，则内部三连通的平面图G在6n x n2网格上绘制凸网格。我们还提出了一种在线性时间内找到这样的图的算法。

项目成果

内部3連結平面グラフの外k 角格子凸描画

内三连通平面图外k角点阵凸图

• 发表时间: 2012
• 作者: Keisuke Tanaka;Akihiro Yamada;and Kenji Yasunaga;Akitoshi Kawamura and Stephen Cook;三浦 一之
• 通讯作者: 三浦 一之

内部3連結グラフの外6角格子凸描画

内三连通图的外六角格凸图

• 发表时间: 2013
• 作者: Hitoshi Namiki;Keisuke Tanaka;and Kenji Yasunaga;三浦 一之
• 通讯作者: 三浦 一之

内部3連結平面グラフの 外ｋ角格子凸描画

内三连通平面图外k角点阵凸图

• 发表时间: 2012
• 作者: A. Kawamura;H. Ota;C. Rosnick;and M. Ziegler;三浦一之
• 通讯作者: 三浦一之

グラフの平面判定アルゴリズムのシミュレーション

图平面确定算法仿真

• 发表时间: 2012
• 作者: 今井純貴;三浦一之
• 通讯作者: 三浦一之

根付き木描画アルゴリズムのシミュレーション

有根树绘制算法模拟

• 发表时间: 2012
• 作者: 大内和樹;三浦一之
• 通讯作者: 三浦一之