Grid embedding of 4-connected plane graphs

被引：29
作者：
He, X
机构：
[1] Department of Computer Science, Stt. Univ. of New York at Buffalo, Buffalo
来源：
DISCRETE & COMPUTATIONAL GEOMETRY | 1997年 / 17卷 / 03期
关键词：
Plane Graph; External Face; Forward Edge; Candidate Vertex; Stable Vertex;
D O I：
10.1007/PL00009290
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as nonintersecting straight line segments. In this paper we show that if a 4-connected plane graph G has at least four vertices on its external face, then G can be embedded on a grid of size W x H such that W + H less than or equal to n, W less than or equal to (n + 3)/2 and H less than or equal to 2(n - 1)/3, where n is the number of vertices of G. Such an embedding can be computed in linear time.
引用
收藏
页码：339 / 358
页数：20
相关论文
共 26 条
[1]  
[Anonymous], 1948, Acta Sci. Math. Szeged, V11, P229
[2]  
[Anonymous], ABSTR AM MATH SOC
[3]  
BONDY JA, 1996, GRAPH THEORY APPLICA
[4]  
CHIBA N, 1982, PROGRESS GRAPH THEOR, P153
[5]  
CHROBAK M, 1993, RUUCS9345 UTR U DEP
[6]  
Chrobak M., 1994, LECT NOTES COMPUTER, V894, P104
[7]  
CHROBAK M, 1989, UCRCS891 U CAL RIV D
[8]   HOW TO DRAW A PLANAR GRAPH ON A GRID [J].
DEFRAYSSEIX, H ;
PACH, J ;
POLLACK, R .
COMBINATORICA, 1990, 10 (01) :41-51
[9]  
EADES P, 1993, ALGORITHMS AUTOMATIC
[10]  
Even S., 1979, Graph Algorithms
123