5.1 Introduction

Some planar graphs can be drawn in such a way that each edge is drawn as a straight line segment and each face is drawn as a convex polygon, as illustrated in Figs. 1.5(b) and 5.1(b). Such a drawing is called a convex drawing. The drawings in Figs. 5.1(d) and (f) are not convex drawings. Although not every planar graph has a convex drawing, Tutte showed that every 3-connected planar graph has a convex drawing, and obtained a necessary and sufficient condition for a plane graph to have a convex drawing [Tut60]. Furthermore, he gave a barycentric mapping method for finding a convex drawing of a plane graph, which requires solving a system of O(n) linear equations [Tut63]. The system of equations can be solved either in O( n ³) time and O( n ²) space using the ordinary Gaussian elimination method, or in O( n ^1.5) time and O( n log n) space using the sparse Gaussian elimination method [LRT79]. Thus the barycentric mapping method leads to an O( n ^1.5) time convex drawing algorithm for plane graphs.

Fig. 5.1: Plane graphs and drawings.

In Sections 5.2 and 5.3 we present two linear algorithms for the convex drawing problem of planar graphs: drawing and testing algorithms [CYN84], The former finds a convex drawing of a given plane graph G if there is; it extends a given convex polygonal drawing of the outer...