Grid Embedding of 4-Connected Plane Graphs

He, Xin (1996) Grid Embedding of 4-Connected Plane Graphs. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995 , pp. 287-299(Official URL:

Full text not available from this repository.


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 non-intersecting straight line segments. In this paper, we show that, if a 4-connected plane graph G has at least 4 vertices on its exterior face, then G can be embedded on a grid of size W \times H such that W + H \le n, W \le (n + 3)/2 and H \le 2(n - 1)/3, where n is the number of vertices of G. Such an embedding can be computed in linear time.

Item Type: Conference Paper
Additional Information: 10.1007/BFb0021812
Classifications: P Styles > P.720 Straight-line
G Algorithms and Complexity > G.999 Others

Actions (login required)

View Item View Item