TABLE OF CONTENTS A straight line drawing of a plane graph is a drawing in which each edge is drawn as a straight line segment without edge-crossings, as illustrated in Fig. 1.5. Wagner [Wag36], F ry [Far48] and Stein [Ste51] independently proved that every planar graph G has a straight line drawing. Their proofs immediately yield polynomial-time algorithms to find a straight line drawing of a given plane graph. However, the area of a rectangle enclosing a drawing on an integer grid obtained by these algorithms is not bounded by any polynomial in the number n of vertices in G. In fact, it remained as an open problem for long time to obtain a drawing of area bounded by a polynomial. In 1990, de Fraysseix et al. [FPP90] and Schnyder [Sch90] showed by two different methods that every planar graph of n ?3 vertices has a straight line drawing on an integer grid of size (2 n ?4) ( n ?2) and ( n ?2) ( n ?2), respectively. The two methods can be implemented as linear-time algorithms, and are well known as the shift method and the realizer method, respectively. We present the shift method in Section 4.2 and the realizer method in Section 4.3.
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
