Lecture Five: Wagner's Theorem Every planar graph has a planar drawing constructed using just straight lines.

  • Def - a max planar graph (mpg) is a planar graph such that the addition of any addtional edge makes the graph non-planar. Example: K5-{e}

  • Prop - If G = (V,E) is mpg, V >= 3, then all regions are triangles

  • Prop - If G = (V,E) is mpg, V >= 4, then all vertices have degree >= 3

  • Prop - If G = (V,E) is mpg, then E = 3V-6

  • Prop - If G = (V,E) is any planar graph, then at least one vertex has degree <= 5

  • Prop - If G = (V,E) is mpg, V >= 4, then there are at least 4 vertices of degree <= 5.

Proof: Let pk = # of vertices of degree exactly k. Then: V = p3 + p4 + p5 +...; 2E = 3p3 + 4p4 + 5p5+...; add fact E = 3V=6, stir.

  • Thm - Straight line drawings always possible.

Proof: Just work with mpgs. Induction on n = V. Base: n = 4. Induction step: If G has V = n+1, must have internal vertex of degree <=5. Delete it, add in a few arcs (maybe to make it new mpg, with n verts. Do line drawing of this. Find the "hole" you made by deletion (remove added marked edges).Then: just place deleted vert, hook it up( will always work, because at worst hole is a non-convex pentagon)

-- RobbieMoll - 21 Sep 2006

Topic revision: r1 - 2006-09-21 - RobbieMoll
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback

mersin escort adana escort izmir escort gaziantep escort