- 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

Edit | Attach | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions

Topic revision: r1 - 2006-09-21 - RobbieMoll

Copyright © 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

Ideas, requests, problems regarding UMass CS EdLab? Send feedback