A study of rectangle-of-influence drawing algorithms of plane graphs

平面图影响矩形绘制算法的研究

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

A drawing of a plane graph G is called a rectangle-of-influence drawing if all vertices of G are put on plane grid points, all edges are drawn as straight line segments without any edge-intersection and there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of every edge. In this study, I improve a sufficient condition for a plane graph G to have a rectangle-of-influence drawing, and present a linear time algorithm to construct a rectangle-of-influence drawing of G on (n-1) x (n-1) integer grid if G satisfies the condition.

一个平面图G的图称为影响矩形图，如果G的所有顶点都放在平面格点上，所有边都画成没有任何边相交的直线段，并且在由每条边的两端定义的平行于轴的矩形的固有内部没有顶点。本文改进了平面图G具有影响矩形图的一个充分条件，并给出了一个线性时间算法来构造G在（n-1）x（n-1）整数网格上的影响矩形图.

项目成果

内部三角化平面グラフの開矩形勢力描画

内三角平面图开矩形受力图

• 发表时间: 2010
• 作者: 木村文也;三浦一之
• 通讯作者: 三浦一之

Sufficient Condition for Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs

内三角平面图开影响矩形图的充分条件

• 发表时间: 2010
• 作者: Kazuyuki Miura;Fumiya Kimura
• 通讯作者: Fumiya Kimura

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

内三连通图的外五边格凸图

• 发表时间: 2011
• 作者: 千葉智子;三浦一之
• 通讯作者: 三浦一之

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

内部三连通图的格子凸图

• 发表时间: 2012
• 期刊: 電子情報通信学会論文誌D
• 作者: 西関隆夫;橋本友也
• 通讯作者: 橋本友也