10Planar GraphsContents10.1 Plane and Planar Graph郑国界务时药桥网务西界湖有有时标技药务会HEORDANRUEHEORESUBDIVISIONS10.2 Duality .ACESDUADELETION-CCNDUALPVECTORSPACESANDDUALITY10.3 Euler's Formula10.4BridgeUOUE10.5 KMINORSWAGNER'S THEOREIZECNIZINGPLANARG10.68NTHEORIENTABLEEMBEDDINGCONJECTURE必究10.7RelatedReadingGRAPHMINORSLIN+:BRAMBLEAMATROIDMINOR10.1 Plane and Planar GraphsA graph is said to be embeddable in the plane, or planar, if it can be drawn inthe plane so that its edges intersect only at their ends. Such a drawing is called10 Planar Graphs Contents 10.1 Plane and Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 243 The Jordan Curve Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 244 Subdivisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 10.2 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Faces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Duals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 Deletion–Contraction Duality . . . . . . . . . . . . . . . . . . . . . . 254 Vector Spaces and Duality . . . . . . . . . . . . . . . . . . . . . . . . . . 256 10.3 Euler’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 10.4 Bridges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 Bridges of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 Unique Plane Embeddings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 10.5 Kuratowski’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 Minors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 Wagner’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 Recognizing Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 271 10.6 Surface Embeddings of Graphs . . . . . . . . . . . . . . . . . . . . 275 Orientable and Nonorientable Surfaces . . . . . . . . . . . . . 276 The Euler Characteristic . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 The Orientable Embedding Conjecture . . . . . . . . . . . . . . 280 10.7 Related Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Graph Minors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Linkages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Brambles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Matroids and Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Matroid Minors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 10.1 Plane and Planar Graphs A graph is said to be embeddable in the plane, or planar, if it can be drawn in the plane so that its edges intersect only at their ends. Such a drawing is called