10.1Plane and Planar Graphs247that, for every surface S, there exist graphs which are not embeddable on s.Every graphcan, however, be embedded in the 3-dimensional euclidean space R(Exercise 10.1.7).Planar graphs and graphs embeddable on the sphere are one and the same. Tosee this, we make use of a mapping known as stereographic projection. Considera sphere S resting on a plane P, and denote by z the point that is diametricallyopposite the point of contact of S and P.The mapping : SI(z] - P,defined byr(s) = p if and only if the points z, s, and p are collinear, is called a stereographicprojection from z; it is illustrated in Figure 10.5.Fig.10.5. Stereographic projectionTheorem 10.4 A graph G is embeddable on the plane if and only if it is embed-dableonthesphereProof Suppose that G has an embedding G on the sphere. Choose a point z ofthe sphere not in G. Then the image of G under stereographic projection from zis an embedding of G on the plane, The converse is proved similarly.口On many occasions, it is advantageous to consider embeddings of planar graphson the sphere; one instance is provided by the proof of Proposition 10.5 in the nextsection.Exercises+10.1.1 Show that:a) every proper subgraph of K3.3 is planar.b)K3.3isnonplanar10.1.2 Show that a graph is planar if and only if every subdivision of the graphis planar.10.1 Plane and Planar Graphs 247 that, for every surface S, there exist graphs which are not embeddable on S. Every graph can, however, be embedded in the 3-dimensional euclidean space R3 (Exercise 10.1.7). Planar graphs and graphs embeddable on the sphere are one and the same. To see this, we make use of a mapping known as stereographic projection. Consider a sphere S resting on a plane P, and denote by z the point that is diametrically opposite the point of contact of S and P. The mapping π : S \{z} → P, defined by π(s) = p if and only if the points z, s, and p are collinear, is called a stereographic projection from z; it is illustrated in Figure 10.5. z s p Fig. 10.5. Stereographic projection Theorem 10.4 A graph G is embeddable on the plane if and only if it is embed￾dable on the sphere. Proof Suppose that G has an embedding G on the sphere. Choose a point z of the sphere not in G. Then the image of G under stereographic projection from z is an embedding of G on the plane. The converse is proved similarly.
On many occasions, it is advantageous to consider embeddings of planar graphs on the sphere; one instance is provided by the proof of Proposition 10.5 in the next section. Exercises 10.1.1 Show that: a) every proper subgraph of K3,3 is planar, b) K3,3 is nonplanar. 10.1.2 Show that a graph is planar if and only if every subdivision of the graph is planar