Planar Graph_Graph Theory Course_presentationslide

Graph Theory

1. Planar Graph

2. Three Utilities Problem Can each house be connected to each utility, with no connection lines crossing?

3. Three Utilities Problem Can each house be connected to each utility, with no connection lines crossing ? NOT Possible

4. Planar Graph Definition: A planar graph is a graph that can be drawn in the plane without crossings - that no two edges intersect geometrically except at a vertex to which both are incident. Any such drawing is called a plane drawing. Figure: (a) Planar graph K 4 Figure: (b) Two plane drawing of K 4

5. Examples of Planar Graph Figure: (a) Cube graph Q 3

6. Examples of Planar Graph Figure: (a ) K 1,5 Figure: (a ) K 2,4 Figure: (a ) C 6

7. Examples of Non-Planar Graph Figure: (a ) K 5 Figure: (b) K 3,3

8. Detection of Planarity Since addition/removal of self loops does not effect planarity, remove all self loops Eliminate edges in parallel by removing all but one edge between every pair of vertices Elimination of a vertex of degree two by merging two edges in series The resultant graph: Single edge K 4 Non-separable simple graph with n>=5 and e>= 7 Then check if e <= 3n-6 satisfies The graph is Planar The graph is Planar

9. Kuratowski's Theorem: Planarity Testing THEOREM: ( Kuratowski , 1930). A graph is planar if and only if it contains no subgraph homeomorphic to K 5 or K 3,3 . Homeomorphism : Two graphs G and G’ are homeomorphic if there is an isomorphism from some subdivision of G to some subdivision of G’

10. Kuratowski's Theorem: Planarity Testing Show that the Petersen graph is non-planar:

11. Euler’s Theorem For a connected planar simple graph with n vertices, m edges and f faces, then n-m+f = 2 . Proof: Case:1 Suppose that m =0.Then for G to be a connected plane graph there must be only one vertex and one face. So, n=1, m=0, f=1. Now, n-m+f = 1-0+1 = 2 Case:2 For m=1, there n=1 m=1 f=2. Now, n-m+f = 1-1+2 = 2 For m=1, there n=2 m=1 f=1 Now, n-m+f = 2-1+1= 2 Case:3 If G is tree, then there m=n-1, f=1. Now, n-m+f = n-(n-1)+1= 2 Tree

12. Euler’s Theorem For a connected planar simple graph with n vertices, m edges and f faces, then n-m+f = 2 . Proof: Case:4 If G is not a tree, then remove an edge ‘e’ belonging to some circuits. After removing the edge ‘e’, we left with a planar graph H on n vertices and (m-1) edges. Denote the number of vertices of H by n H , edges by m H and faces by f H . Now n H = n. m H = m-1, f H = f-1 2 = n H – m H + f H = n-m+1+f-1 = n-m+f Thus, n-m+f = 2 G H

13. Corollary If G is a connected simple finite plane graph with n vertices (n≥ 3), then G has at most (3n-6) edges. Furthermore, if G contains no triangles, then G has at most (2n-4) edges. Proof: Suppose that G has m edges and f faces consider the number of pairs (e, F) where, e is one of the edges bounding the face F. For each edge, there are at most 2 faces that it bounds. So the total number of edge-face pairs have to be less than 2m. On the other hand, because G is a simple graph, each face is bounded by at least 3 edges. So the total number of edge face pairs is greater than or equal to 3f. 3f ≤ 2m . Now from Euler’s Theorem n-m+f = 2 3n – m +3f =6 3f = 6-3n+3m 2m 6-3n+3m 2m-3m ≥ 6-3n - m ≥ 6-3n m≤ 3n-6 [Multiplied by -1] Try by yourself: If G contains no triangles, then G has at most (2n-4) edges. e 1 e 2 e 3 e 4 e 5 e 5 e 6 e 7 e 8 e 9 e 10 F 1 F 2 F 3 F 4 F 5 Infinite face Here, n=8 m=10 and f = 5 No. of edge face pairs = 19 19 ≤ 2*10 19 ≥ 3*5