Minimum-width grid drawings of plane graphs
Minimum-width grid drawings of plane graphs
复制标题
平面图的最小宽度网格图
DOI：
10.1016/s0925-7721(98)00016-9
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Shin
中科院分区：
文献类型：
--
作者：
M. Chrobak;Shin
给定一个平面图G，我们希望在平面上画它，使得G的顶点表示为网格点，边表示为端点之间的直线段。另一个目标是最小化所得到的网格的大小。众所周知，每个平面图都可以在一个（n-2）×（n-2）网格中以这种方式绘制（n ≥ 3），并且如果n是3的倍数，则没有小于（2n 3 - 1）×（2n 3 - 1）的网格可以用于此目的。事实上，对于所有n ≥ 3，所得到的网格的每个维度都需要至少为<$2（n − 1）3 <$，即使另一个维度允许是无界的。在本文中，我们通过提出一个网格绘制算法来证明这个界限是紧的，该算法可以生成宽度为的图形。绘制的图形的高度以4 <$2（n-1）3 <$-1为界。我们的算法运行在线性时间，易于实现。
Given a plane graph G, we wish to draw it in the plane in such a way that the vertices of G are represented as grid points, and the edges are represented as straight-line segments between their endpoints. An additional objective is to minimize the size of the resulting grid. It is known that each plane graph can be drawn in such a way in an (n − 2) × (n − 2) grid (for n ≥ 3), and that no grid smaller than ( 2n 3 − 1) × ( 2n 3 − 1) can be used for this purpose, if n is a multiple of 3. In fact, for all n ≥ 3, each dimension of the resulting grid needs to be at least ⌞ 2(n − 1) 3 ⌟ , even if the other one is allowed to be unbounded. In this paper we show that this bound is tight by presenting a grid drawing algorithm that produces drawings of width ⌞ 2(n − 1) 3 ⌟ . The height of the produced drawings is bounded by 4⌞ 2(n − 1) 3 ⌟ − 1 . Our algorithm runs in linear time and is easy to implement.