# Introduction

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. 


# Definition

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
f 1 =3, deg f 2 =4, deg f 3 =3, deg f 4 =7, f 5 =4
. 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.


# III.

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.


# Proof

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] 
( D D D D ) F 2012 Year v0(x0, y0) v1(x1, y1) v2(x2, y2) v3(x3, y3) v3(x3, y3) v0(x0, y0) v1(x1, y1) v2(x2, y2) - - - - ++ + + z z y x x y v0(x0, y0) v1(x1, y1) v2(x2, y2) v3(x3, y3) v4(x4, y4) v5(x5, y5) v0(x0, y0) v1(x1, y1) v2(x2, y2) v3(x3, y3) v4(x4, y4) v5(x5, y5) - - - - - + +

# Conclusions

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: 
1112![Figure 1.1 : Convex drawing of planar graph](image-2.png "Figure 1 . 1 :Figure 1 . 2 :")









BeginStep 1: Check input planar graph has curved edges.if (curved edges)then replace curved edges by straightline edges.elsego to step 2.end if2012 YearStep 2: Step 3.3(a): if ( cross product C j = 0)then go to step 5.elsego to step 3(b).end if.3(b):if (j=0)then increment j by 1.elsecheck cross product C j and C j-1 are same sign.D D D D ) Fif (cross product C j and C j-1 are same sign) then increment j by 1. else(go to step 5.end ifend ifend doend for.go to step 4.Step 4: End? We develop a linear time algorithm for examiningwhether a planar graph has a convex drawing ornot. One can develop an algorithm for convertingnon-convex drawing of a planar graph to convexdrawing.? One can develop a convex grid drawing of a planargraph on an (n-2) x (n-2) grid.
			© 2012 Global Journals Inc. (US)Global Journal of Computer Science and Technology
		
		
			

				


* 
	
		Planar Graph Drawing
		
			Md
		
		
			TakaoShaidur Rahman
		
		
			Nishizeki
		
		
	




* 
	
		1-bend orthogonal drawing from tri-connected planar 4-graph
		
			AH M AHabib
		
		
			MSRahman
		
		
			Buet
		
		
			Bngladesh
		
		
			2007
		
	




* 
	
		On the minimum ranking edge tree problem series parallei graph
		
			MiaArefin
		
	
	
		Ser. B
		
			80
			
			2008
		
	
	which crossing number is it anyway?




* 
	
		Crossing number is NP-complete
		
			MRGray
		
		
			DSJohnson
		
	
	
		SIAM J. Algeric and Discrete Methods
		
			4
			
			1983
		
	




* 
	
		Convex representations of graphs
		
			WTTutte
		
	
	
		Proc. London Math.SOC
		
			10
			
			1960
		
	




* 
	
		How to draw a graph
		
			WTTutte
		
	
	
		Proc. of London Math. SOC
		
			13
			
			1963
		
	




* 
	
		Generalized nested dissections
		
			RJLipton
		
		
			DJRose
		
		
			RETarjan
		
	
	
		SIAM J. Numer. Anal
		
			16
			2
			
			1979