TABLE OF CONTENTS We have seen two algorithms in the previous two sections to find a straight line drawing on grids of sizes (2 n ?4) ( n ?2) and ( n ?2) ( n ?2), respectively. A natural question arises: what is the minimum size of a grid required for a straight line drawing? de Fraysseix et al. showed that, for each n ?3, there exists a plane graph of n vertices, for example nested triangles, which needs a grid of size at least [2( n ?1)/3] [2( n ?1)/3] for any grid drawing [CN98, FPP90]. It has been conjectured that every plane graph of n vertices has a grid drawing on a [2 n/3] [2 n/3] grid, but it is still an open problem. On the other hand, a restricted class of graphs has a more compact grid drawing. For example, if G is a 4-connected plane graph, then G has a more compact grid drawing [He97, MNN01]. In this section we consider compact straight line grid drawings of 4-connected plane graphs.
Let G be a 4-connected plane graph having at least four outer vertices. Miura et al. [MNN01] gave a very simple algorithm which finds a grid drawing of G on a W H grid such that W=[ n/2] ?1 and H=[ n/2] in linear time. Their result is indeed best possible, because there exist an infinite number of...
