图论第六章.ppt

Graph Theory * Kuratowski’s Theorem6.2.2 A graph is planar if and only if it does not contain a subdivision of K5 or K3,3 Graph Theory * Lemma 6.2.4 If F is the edge set of a face in a planar embedding of G, then G has an embedding with F being the edge set of the unbounded face Graph Theory * Planarity test Successively add paths from current fragments to check if the graph can be drawn without crossing. Graph Theory * Five Color Theorem Heawood[1890] Every planer graph is 5–colorable. Graph Theory * Theorem Appel-Haken-Koch[1977] 6.3.6 Every planar graph is 4-colorable. The proof used configurations with ring size up to 14. A ring of size 13 has 66430 distinguishable 4-colorings Reducibility requires showing that each leads to a 4-coloring of the full graph Using 1000 hours of computer time in 1976, they found an unavoidable set of 1936 reducible configurations, all with ring size at most 14 Ch. 6. Planar Graphs Planar Graphs Graph Theory * Chapter 6 Planar Graphs Graph Theory * Drawings in the plan Can a graph be drawn in a plane without edge crossings? Graph Theory * Proposition 6.1.2: K5 and K3,3 cannot be drawn without crossings Proof: Considers a drawing of K5 or K3,3 in the plane. Let C be a spanning cycle. ? A B C D E A B D C E F A B D C E F Graph Theory * Proposition 6.1.2: K5 and K3,3 cannot be drawn without crossings Proof: (continue) If the drawing does not have crossing edges, then C is drawn as a closed curve. Chords of C must be drawn inside or outside this curve. Two chords conflict if their endpoints on C occur in alternating order. When two chords conflict, we can draw only one inside C and one outside C. ? A B C D E Chord Graph Theory * Proposition 6.1.2: K5 and K3,3 cannot be drawn without crossings Continued Proof: continued A 6-cycle in K3,3 has three pairwise conflicting chords. We can put at most one inside and one outside, so it is not possible to complete the embedding. When C is a 5-cycle in K5, at most two chords c