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.