Grid embedding of 4-connected plane graphs

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.