TABLE OF CONTENTS In this section we describe a constructive proof for the theorem by de Fraysseix et al. [FPP90] that every plane graph G of n ?3 vertices has a straight line grid drawing of size (2 n ?4) ( n ?2), and present a linear-time implementation of an algorithm for finding such a drawing [CP95]. If G is not triangulated, then we obtain a triangulated plane graph G ? from G by adding dummy edges to G. From a straight line grid drawing of G' we can immediately obtain a straight line grid drawing of G by deleting the dummy edges. Therefore it is sufficient to prove that a triangulated plane graph G of n vertices has a straight line grid drawing of size (2 n ?4) ( n ?2). To construct such a drawing, de Fraysseix et al. introduced an ordering of vertices called a canonical ordering and installed vertices one by one in the drawing according to the ordering.
In Section 4.2.1 we present a canonical ordering, and in Section 4.2.2 we present the algorithm of de Fraysseix et al. We present a linear time implementation of the algorithm in Section 4.2.3.
For a cycle C in a graph, an edge joining two non-consecutive vertices in C is called a chord of C. For a 2-connected plane graph G, we denote by C
