Rectangular grid drawings of plane graphs
Rectangular grid drawings of plane graphs
复制标题
平面图的矩形网格图
DOI：
10.1016/s0925-7721(98)00003-0
复制
发表时间：
1996
影响因子：
1.8
通讯作者：
Takao Nishizeki
中科院分区：
文献类型：
--
作者：
M. S. Rahman;Shin;Takao Nishizeki
平面图G的矩形网格图是G的一种图，使得每个顶点位于网格点上，每个边被画成水平或垂直线段，并且每个面的轮廓被画成矩形。本文给出了一个简单的线性时间算法来求G的矩形网格图（如果存在）。我们还给出了G的要求宽W和要求高H之和的上界W + H ≤ n2，以及G的矩形网格图面积的上界WH ≤ n216，其中n是G的顶点数.这些边界是最好的，并且适用于任何紧凑的矩形网格绘图。
The rectangular grid drawing of a plane graph G is a drawing of G such that each vertex is located on a grid point, each edge is drawn as a horizontal or vertical line segment, and the contour of each face is drawn as a rectangle. In this paper we give a simple linear-time algorithm to find a rectangular grid drawing of G if it exists. We also give an upper bound W + H ≤ n 2 on the sum of required width W and height H and a bound W H ≤ n216 on the area of a rectangular grid drawing of G, where n is the number of vertices in G. These bounds are best possible, and hold for any compact rectangular grid drawing.