Chapter 2   Planar graphs

 A graph is planar if it can be drawn in the plane in such a way that no edges intersect, except of course at a common endvertex. Planar graphs corresponding to the regular polyhedra and other geometric figures have been investigated since the time of the ancient Greeks. Several mathematical works from the 18th and the 19th Century exhibit properties of graphs corresponding to convex 3-polyhedra. A classical example is Euler's polyhedral formula. A more recent cornerstone in geometry is Steintz' theorem that the 3-connected planar graphs are the 1-skeletons of convex polyhedra in the 3-space. Planar graphs also appear in some applied disciplines. An example is VLSI design where one would like to design a large electric network on a planar electric board so that the connections between the components of the network do not intersect (or intersect as little as possible). Some results on planar graphs were inspired by such practical problems. However, the main source of inspiration for planar graphs was the Four Color Conjecture (now Theorem; cf. Chapter 8) that the vertices of any planar graph can be colored with four colors in such a way that no two adjacent vertices have the same color.

Several books and surveys contain results on planar graphs. We refer, for example, to Tutte [Tu84]. Algorithmic aspects are treated in [NC88, Wi85, Ya95]. Kelmans' survey [Ke93] includes material that has been published only in Russian journals. Of course, the Four Color Problem, which is the subject of the monographs [AH89, Ore67, SK77], involves some theory on planar graphs.

In this chapter we concentrate on a few fundamental results which are useful when going to higher surfaces. We also present rigorous proofs of the topological prerequisites for studying graphs in the plane and on surfaces beginning with the Jordan Curve Theorem, which says that a simple closed curve in the Euclidean plane partitions the plane into precisely two parts: the interior and the exterior part of the plane. Although this fundamental result seems intuitively obvious, it is fascinatingly difficult to prove. There are several proofs in the literature. A relatively elementary proof (involving only approximation with polygons) has been published by Tverberg [Tv80]. Our proof is taken from [Th92]. Apart from very basic point set topology and a few simple properties of the plane, it uses only basic tools from graph theory. The properties of the plane needed in our proof are that R2 is an arcwise connected Hausdorff space, that K3,3 cannot be embedded in R2, and that no simple arc separates R2. These properties are indeed sufficient for every simple closed curve in a topological space X to separate X as shown in [Th90a]. These ideas are used in [Th90d] to obtain a characterization of the 2-sphere in terms of Jordan curve separation. They are presented in Section 2.10.

We also present the short proof by Thomassen [Th92] of the Jordan-Schoenflies Theorem which says that a homeomorphism of a simple closed curve in the plane onto a circle in the plane can be extended to a homeomorphism of the entire plane. Again, this result seems intuitively clear but a rigorous proof involves a number of technical details. While the Jordan Curve Theorem is also valid for spheres in R3, the Jordan-Schoenflies Theorem does not extend to R3 (as shown by the so-called Alexander Horned Sphere, see, e.g., Moise [Mo77]).

Sections 2.3 - 2.8 give basic combinatorial and geometric results about planar graphs: We present a short proof of Kuratowski's Theorem which characterizes planar graphs in terms of forbidden subgraphs. Several other characterizations of planar graphs are presented. We establish many properties of planar graphs and discuss various kinds of representations of planar graphs. In Section 2.8 we give a proof of the Koebe-Andreev-Thurston Circle Packing Theorem in a very strong primal dual version due to Brightwell and Scheinerman [BS93]. This result has important applications. In particular, a short proof of Steinitz' theorem is derived. In Section 2.9 we indicate how Rodin and Sullivan [RS87] used it to give a simpler constructive proof of the Riemann Mapping Theorem.