Mathematics for Computer Science
12 Planar Graphs 12.1 Drawing Graphs in the Plane Suppose there are three dog houses and three human houses, as shown in Fig- ur ...
Chapter 12 Planar Graphs474 Figure 12.1 Three dog houses and and three human houses. Is there a route from each dog house to eac ...
12.2. Definitions of Planar Graphs 475 Figure 12.2 Five quadrapi (4-armed creatures). (a) (b) Figure 12.3 K3;3(a) andK 5 (b). Ca ...
Chapter 12 Planar Graphs476 v u (a) u v (b) Figure 12.4 Planar drawings of (a)K3;3withouthu—vi, and (b)K 5 without hu—vi. Steve ...
12.2. Definitions of Planar Graphs 477 curves cross themselves or other curves, namely, the only points that appear more than on ...
Chapter 12 Planar Graphs478 II I III IV Figure 12.5 A planar drawing with four continuous faces. d c b a II I III IV Figure 12.6 ...
12.2. Definitions of Planar Graphs 479 b e f g c d a Figure 12.7 A planar drawing with abridge. Unfortunately, continuous faces ...
Chapter 12 Planar Graphs480 s t u r v x y w Figure 12.8 A planar drawing with adongle. vertices —not what a drawing of the graph ...
12.2. Definitions of Planar Graphs 481 y w a z b x Figure 12.9 The “split a face” case:awxbyzasplits intoawxbaandabyza. Construc ...
Chapter 12 Planar Graphs482 z b t v a x y u w Figure 12.10 The “add a bridge” case. Then the graph obtained by connectingGandHwi ...
12.2. Definitions of Planar Graphs 483 s t r u u t r s Figure 12.11 Two illustrations of the same embedding. stick to the idea o ...
Chapter 12 Planar Graphs484 12.3 Euler’s Formula The value of the recursive definition is that it provides a powerful technique ...
12.4. Bounding the Number of Edges in a Planar Graph 485 graph withvGCvHvertices,eGCeHC 1 edges, andfGCfH 1 faces. Since .vGCvH/ ...
Chapter 12 Planar Graphs486 Butf DevC 2 by Euler’s formula, and substituting into (12.4) gives 3.evC2/2e e3vC 6 0 e3v 6 12 ...
12.6. Coloring Planar Graphs 487 for any embedding of a planar bipartite graph. By Euler’s theorem,fD 2 vCe. Substituting 2 vCef ...
Chapter 12 Planar Graphs488 n 2 n 1 n 2 n 1 !! m Figure 12.12 Merging adjacent verticesn 1 andn 2 into new vertex,m. Theorem 12. ...
12.7. Classifying Polyhedra 489 be two neighbors,n 1 andn 2 , ofgthat are not adjacent. Now mergen 1 and ginto a new vertex,m. I ...
Chapter 12 Planar Graphs490 (a) (b) (c) Figure 12.13 The tetrahedron (a), cube (b), and octahedron (c). v (a) (b) (c) Figure 12. ...
12.7. Classifying Polyhedra 491 n m v e f polyhedron 3 3 4 6 4 tetrahedron 4 3 8 12 6 cube 3 4 6 12 8 octahedron 3 5 12 30 20 ic ...
Chapter 12 Planar Graphs492 12.8 Another Characterization for Planar Graphs We did not pick K 5 andK3;3as examples because of th ...
«
20
21
22
23
24
25
26
27
28
29
»
Free download pdf