24410 Planar Graphsa planar embedding of the graph. A planar embedding G of aaplrgraphGcanbe regarded as a graph isomorphic to G; the vertex set of G is the set of pointsrepresenting the vertices of G, the edge set of G is the set of lines representing theedges of G, and a vertex of G is incident with all the edges of G that contain it.For this reasowe often refertoaplanar embedding Gof aplanargraphGasaplane graph, and we refer to its points as vertices and its lines as edges. Howeverwhen disc both a planar graph G and a plane embedding G of G, in orderto distinguish the two graphs, we call the vertices of G points and its edges linesthus, by the point of Gwe mean the point of Gthat represents the vertex ofG, and by the line e of G we mean the line of G that represents the edge e ofG. Figure 10.1b depicts a planar embedding of the planar graph K, Ie, shown inFigure 10.la.(6)(a)Fig. 10.1. (a) The planar graph Ks /e, and (b) a planar embedding of Ks /eTHE JORDAN CURVE THEOREMIt is evident from the above definition that the study of planar graphnecessarilyinvolves the topology of the plane. We do not attempt here to be strictly rigorous intopological matters, however, and are content to adopt a naive point of view towardthem. This is done so as not to obscure the combinatorial aspects of the theorywhich is our main interest. An elegant and rigorous treatment of the topologicalaspectscanbefoundinthebookbyMoharandThomassen(2001)The results of topology that are especially relevant in the study of planar graphsare those which deal with simple curves. By a curve, we mean a continuous imageof aclosed unitlient.Analogously,closed curveisacontlousimageofa circle. A curve or closed curve is simple if it does not intersect itself (in otherwords, if the mapping is oneto-one).Properties of such curves come into play inthestudyofplanargraphsbecausecvclesinplanegraphsaresimpleclosedcurvesA subset of the plane is arcwise-connected if any two of its points can beconnected by a curve lying entirely within the subset. The basic result of topologythat we need is the Jordan Curve Theorem.244 10 Planar Graphs a planar embedding of the graph. A planar embedding G of a planar graph G can be regarded as a graph isomorphic to G; the vertex set of G is the set of points representing the vertices of G, the edge set of G is the set of lines representing the edges of G, and a vertex of G is incident with all the edges of G that contain it. For this reason, we often refer to a planar embedding G of a planar graph G as a plane graph, and we refer to its points as vertices and its lines as edges. However, when discussing both a planar graph G and a plane embedding G of G, in order to distinguish the two graphs, we call the vertices of G points and its edges lines; thus, by the point v of G we mean the point of G that represents the vertex v of G, and by the line e of G we mean the line of G that represents the edge e of G. Figure 10.1b depicts a planar embedding of the planar graph K5 \ e, shown in Figure 10.1a. (a) (b) Fig. 10.1. (a) The planar graph K5 \ e, and (b) a planar embedding of K5 \ e The Jordan Curve Theorem It is evident from the above definition that the study of planar graphs necessarily involves the topology of the plane. We do not attempt here to be strictly rigorous in topological matters, however, and are content to adopt a naive point of view toward them. This is done so as not to obscure the combinatorial aspects of the theory, which is our main interest. An elegant and rigorous treatment of the topological aspects can be found in the book by Mohar and Thomassen (2001). The results of topology that are especially relevant in the study of planar graphs are those which deal with simple curves. By a curve, we mean a continuous image of a closed unit line segment. Analogously, a closed curve is a continuous image of a circle. A curve or closed curve is simple if it does not intersect itself (in other words, if the mapping is one-to-one). Properties of such curves come into play in the study of planar graphs because cycles in plane graphs are simple closed curves. A subset of the plane is arcwise-connected if any two of its points can be connected by a curve lying entirely within the subset. The basic result of topology that we need is the Jordan Curve Theorem