Introduction to Graphs

Introduction to Graphs

Chapter 10.7 Planar Graphs These class notes are based on material from our textbook, Discrete Mathematics and Its Applications, 7th ed., by Kenneth H. Rosen, published by McGraw Hill, Boston, MA, 2011. They are intended for classroom use only and are not a substitute for reading the textbook. The House-and-Utilities Problem Planar Graphs

Consider the previous slide. Is it possible to join the three houses to the three utilities in such a way that none of the connections cross? Planar Graphs Phrased another way, this question is equivalent to: Given the complete bipartite graph K 3,3, can K3,3 be drawn in the plane so that no two of its edges cross? K3,3

Planar Graphs A graph is called planar if it can be drawn in the plane without any edges crossing. A crossing of edges is the intersection of the lines or arcs representing them at a point other than their common endpoint. Such a drawing is called a planar representation of the graph. Example A graph may be planar even if it is usually drawn with crossings, since it may be possible to draw it in another way without

crossings. Example A graph may be planar even if it represents a 3-dimensional object. Planar Graphs We can prove that a particular graph is planar by showing how it can be drawn without any crossings. However, not all graphs are planar. It may be difficult to show that a graph is nonplanar. We would have to show that

there is no way to draw the graph without any edges crossing. Regions Euler showed that all planar representations of a graph split the plane into the same number of regions, including an unbounded region. R4 R3 R2

R1 Regions In any planar representation of K3,3, vertex v1 must be connected to both v4 and v5, and v2 also must be connected to both v4 and v5. v1 v2 v3 v4

v5 v6 Regions The four edges {v1, v4}, {v4, v2}, {v2, v5}, {v5, v1} form a closed curve that splits the plane into two regions, R1 and R2. v1 v5

R2 v R1 v Regions Next, we note that v3 must be in either R1 or R2. Assume v3 is in R2. Then the edges {v3, v4} and {v4, v5} separate R2 into two subregions, R21 and R22.

v1 v5 v1 v5 R21 R2 R1

v3 R22 v v v v

Regions Now there is no way to place vertex v6 without forcing a crossing: If v6 is in R1 then {v6, v3} must cross an edge If v6 is in R21 then {v6, v2} must cross an edge If v6 is in R22 then {v6, v1} must cross an edge v1 v5 R21 v3

R1 R22 Regions Alternatively, assume v3 is in R1. Then the edges {v3, v4} and {v4, v5} separate R1 into two subregions, R11 and R12. v1 v5 R11

R2 v4 R12 v2 v3 Regions Now there is no way to place vertex v6 without forcing a crossing:

If v6 is in R2 then {v6, v3} must cross an edge If v6 is in R11 then {v6, v2} must cross an edge If v6 is in R12 then {v6, v1} must cross an edge v1 v5 R11 R2 v4 R12

v2 v3 Planar Graphs Consequently, the graph K3,3 must be nonplanar. K3,3 Regions Euler devised a formula for expressing the

relationship between the number of vertices, edges, and regions of a planar graph. These may help us determine if a graph can be planar or not. Eulers Formula Let G be a connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G. Then r = e - v + 2. R4

R3 R2 R1 # of edges, e = 6 # of vertices, v = 4 # of regions, r = e - v + 2 = 4 Eulers Formula (Cont.) Corollary 1: If G is a connected planar simple graph with e edges and v vertices where v 3, then e 3v - 6. (no proof)

Is K5 planar? K5 Eulers Formula (Cont.)

K5 has 5 vertices and 10 edges. We see that v 3. So, if K5 is planar, it must be true that e 3v 6. 3v 6 = 3*5 6 = 15 6 = 9. So e must be 9. But e = 10. So, K5 is nonplanar. K5 Eulers Formula (Cont.) Corollary 2: If G is a connected planar simple graph, then G must have a vertex of degree not exceeding 5.

If G has one or two vertices, it is true; thus, we assume that G has at least three vertices. If the degree of each vertex were at least 6, then by Handshaking Theorem, 2e 6v, i.e., e 3v, but this contradicts the inequality from Corollary 1: e 3v 6. 2e deg(v ) vV Eulers Formula (Cont.) Corollary 3: If a connected planar simple graph has e edges and v vertices with v 3 and no

circuits of length 3, then e 2v - 4. (no proof) Is K3,3 planar? Eulers Formula (Cont.) K3,3 has 6 vertices and 9 edges.

Obviously, v 3 and there are no circuits of length 3. If K3,3 were planar, then e 2v 4 would have to be true. 2v 4 = 2*6 4 = 8 So e must be 8. But e = 9. So K3,3 is nonplanar. K3,3

Recently Viewed Presentations

  • FY2017 ICD-10-CM/PCS Update Highlights GeBBS Healthcare Solutions Coding

    FY2017 ICD-10-CM/PCS Update Highlights GeBBS Healthcare Solutions Coding

    The Third International Consensus Definitions for Sepsis and Septic Shock (Sepsis-3) Sepsis is defined as life-threatening organ dysfunction caused by a dysregulated host response to infection.. Septic shock is a subset of sepsis in which underlying circulatory and cellular/metabolic abnormalities...
  • UNIT 3: INPUT, STORAGE AND EDITING AND GIS

    UNIT 3: INPUT, STORAGE AND EDITING AND GIS

    geometry (COGO); and . Conversion . ... However, the distinct rubber sheet algorithm used will vary depending on the spatial data model, vector or raster, employed by the GIS. Some raster techniques may be more intensive than vector based algorithms.
  • Performance of Stone Matrix Asphalt Pavements in Maryland

    Performance of Stone Matrix Asphalt Pavements in Maryland

    News Gothic MT Arial Times New Roman System Modern Symbol Arial Black Blank Presentation.pot Microsoft Clip Gallery Microsoft Word Document No Slide Title No Slide Title No Slide Title No Slide Title No Slide Title No Slide Title No Slide...
  • AVID Journal Prompts

    AVID Journal Prompts

    Journal Instructions Write you journals in the journal section of your AVID binder. You need to practice your BEST writing skills! Journals are not just "work" to do at the beginning of class, they are more than that. These journals...
  • Information Technology Services - edu

    Information Technology Services - edu

    Queensland University of Technology EDUCAUSE 2002 ... Imaging System Library Database Systems Infrastructure Governance INFORMATION VELOCITY AND VERACITY 300 + interfaces QUT Virtual CONCEPT HR/Payroll Oracle Financials Callista Student Specialist Staff/ Process Access Staff and Student Access ...
  •  Project Overview Learning Areas Levels Objectives Mathamatique 16-17-18

    Project Overview Learning Areas Levels Objectives Mathamatique 16-17-18

    Title: L'art des mathématiques Mathamatique Project Overview Learning Areas Levels 16-17-18 ans Apply and Master Different Math Concerpts in Relation with Art Drawings
  • Title of presentation

    Title of presentation

    Achieved a qualification on first language Welsh or English/Literacy and Mathematics/numeracy at level 2 of the National Qualifications framework equivalent to GCSE A-C, or above and they must be able to provide proof of the details of those qualifications.
  • Cascade Principles, Bayes Rule and Wisdom of the

    Cascade Principles, Bayes Rule and Wisdom of the

    Milgram, Bickman, Berkowitz in1960. x number of people stare up. How many passers by will also look up? Increasing social force for conformity? Or expect those looking up to have more information? Information cascades partly explain many imitations in social...