ome 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 Figure 3.1. Such a drawing is called a convex drawing. The drawings in Figs. 3.2 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 [5]. 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 [6]. The system of equations can be solved either in O(n3) time and O(n2) space using the ordinary Gaussian elimination method, or in O(n1.5) time and O(n log n) space using the sparse Gaussian elimination method [LRT79]. Thus the barycentric mapping method leads to an O(n1.5 ) time convex drawing algorithm for planar graphs. In this chapter we first give a lemma for a face is drawn as convex polygon or not. Then using that lemma finally we device a linear time algorithm to examine whether a planar graph has convex drawing or not.

By extensively examining the characteristics of convex drawing of a planar graph we derive a lemma for examining whether a planar graph has convex drawing or not. Before introducing the lemma we need to define some terms. If G is a planar graph, then any plane drawing of G divides the plane into regions, called faces [9]. That is, a face is an area bounded by the edges .One of these faces is unbounded, and is called the infinite face. If f is any face, then the degree of f (denoted by deg f) is the number of edges encountered in a walk around the boundary of the face f. If all faces have the same degree (g, say), the G is face-regular of degree g. For example, the following graph G depicts in Figure 3.4 has six faces, f6 being the infinite face. It is easy to see from above graph that deg

. Note that the sum of all the degrees of the faces is equal to twice the number of edges in the graph, since each edge either borders two different faces (such as bg , cd, and cf) or occurs twice when walk around a single face (such as ab and gh). The Euler's formula relates the number of vertices, edges and faces of a planar graph. If n, m, and f denote the number of vertices, edges, and faces respectively of a connected planar graph, then we get n-m+f = 2.The Euler formula tells us that all plane drawings of a connected planar graph have the same number of faces namely, 2+m-n.

Theorem (Euler's Formula) Let G be a connected planar graph, and let n, m and f denote, respectively, the numbers of vertices, edges, and faces in a plane drawing of G. Then n-m + f = 2.

Proof We employ mathematical induction on edges, m. The induction is obvious for m=0 since in this case n=1 and f=1. Assume that the result is true for all connected plane graphs with fewer than m edges, where m is greater than or equal to 1, and suppose that G has m edges. If G is a tree, then n=m+1 and f=1 so the desired formula follows. On the other hand, if G is not a tree, let e be a cycle edge of G and consider G-e. ? Every internal angle is less than 180 degrees.

? Every line segment between two vertices remains inside or on the boundary of the polygon.

A simple polygon is strictly convex if every internal angle is strictly less than 180 degrees. A face is drawn as convex polygon if and only if the cross products of adjacent edges of each vertex of that face are same sign.

Let, a face is assumed to be described by N vertices ordered by, v 0 (x 0 , y 0 ), v 1 (x 1 , y 1 ), v 2 (x 2 , y 2 ), . . . v n-1 (x n-1 , y n-1 ) Figure 3.6 (a) and (b) depicts a face in clockwise and anti-clockwise vertex ordering respectively. A simple test of vertex ordering for examining a face is drawn as convex polygon is based on considerations of the cross product between adjacent edges of each vertex of that face. If the cross product is positive then it rises above the plane (z axis up out of the plane) and if negative then the cross product is into the plane. cross product = ((x i -x i-1 ), (y i -y i-1 )) x ( ( x i+1 -x i ),(y i+1 -y i ) ) = ( x i -x i-1 ) * ( y i+1 -y i ) -( y i -y i-1 ) * ( x i+1 -x i ) A non-convex face has mixture of cross products sign of adjacent edges of each vertex of that face. Hence, a face is drawn as convex polygon if and only if the cross products of adjacent edges of each vertex of that face are same sign.

[Proved]

In this thesis we have studied the convex drawing of a planar graph. Not every planar graph has convex drawing. The results of this thesis are summarized as follows: ? We have derived a method for determining whether a face is drawn as convex polygon or not. ? Finally, using that method we develop a linear time algorithm for examining whether a planar graph has a convex drawing or not. Some interesting directions in which the future research works can be done are as follows: