27610 Planar GraphsFig. 10.23. The Wagner graphother than the plane and the sphere. In recent years, embeddings have been usedto investigate a wide variety of problems in graph theory, and have proved to bean essential tool in the study of an important graph-theoretic parameter,thetreewidth whose theory was developed in an extensive series of papers by N.Robertsonand P. D. Seymour (see Sections 9.8 and 10.7). The books by Bonnington andLitle (1995),Frechet andFan (2003),Gross and Tucker (1987),and Mohar andThomassen (2001) have excellent acnts of the theory of embeddings of graphsonsurfacesWepresent hereabrief account ofsomeofthe basicnotions andresultsof the subject, without proofs, and without making any attempt to be rigorous.ORIENTABLEAND NONORIENTABLE SURFACESnected 2-dimensional manifold. Apart from the plane and theA surface is asphere, examples of surfaces include the cylinder, the Mobius band, and the torus.The cylinder may be obtained by gluing together two opposite sides of a rectangle,the Mobius band by gluing together two opposite sides of a rectangle after makingone half-twist, and the torus by gluing together the two open ends of a cylinder.The Mobius band and the torus are depicted in Figure 10.24. (Drawings fromCrossley(2005),courtesyMartin Crossley.)Therthose which are orientable and thosetwobasivpes of surface:which are 1norientable. To motivate the distinction betweeenthesetwo typeslet us consider the Mobius band. First note that, unlike what the physical modeisuggests, theMobius band has nothickness'Moreover,unlike the cylinder,iti'one-sided'. Now consider a line running along the middle of a Mobius band, andimagine an ant crawling on the surface along it. After onecompleterevolution,the ant would return to where it started from. However, it would have the curiousexperience of finding its 'left' and ‘right' reversed; those points of the surfacewhich were to the left of the ant at the beginning would now be to its right:it is notposssible to 'globally' distinguish left from right on the Mobius band.Surfaces which have this property are said to be nonontable:allothersurfaceare orientable. The plane, the cylinder, the sphere, and the torus are examples oforientable surfaces276 10 Planar Graphs Fig. 10.23. The Wagner graph other than the plane and the sphere. In recent years, embeddings have been used to investigate a wide variety of problems in graph theory, and have proved to be an essential tool in the study of an important graph-theoretic parameter, the tree￾width, whose theory was developed in an extensive series of papers by N. Robertson and P. D. Seymour (see Sections 9.8 and 10.7). The books by Bonnington and Little (1995), Fr´echet and Fan (2003), Gross and Tucker (1987), and Mohar and Thomassen (2001) have excellent accounts of the theory of embeddings of graphs on surfaces. We present here a brief account of some of the basic notions and results of the subject, without proofs, and without making any attempt to be rigorous. Orientable and Nonorientable Surfaces A surface is a connected 2-dimensional manifold. Apart from the plane and the sphere, examples of surfaces include the cylinder, the M¨obius band, and the torus. The cylinder may be obtained by gluing together two opposite sides of a rectangle, the M¨obius band by gluing together two opposite sides of a rectangle after making one half-twist, and the torus by gluing together the two open ends of a cylinder. The M¨obius band and the torus are depicted in Figure 10.24. (Drawings from Crossley (2005), courtesy Martin Crossley.) There are two basic types of surface: those which are orientable and those which are nonorientable. To motivate the distinction between these two types, let us consider the M¨obius band. First note that, unlike what the physical model suggests, the M¨obius band has no ‘thickness’. Moreover, unlike the cylinder, it is ‘one-sided’. Now consider a line running along the middle of a M¨obius band, and imagine an ant crawling on the surface along it. After one complete revolution, the ant would return to where it started from. However, it would have the curious experience of finding its ‘left’ and ‘right’ reversed; those points of the surface which were to the left of the ant at the beginning would now be to its right: it is not possible to ‘globally’ distinguish left from right on the M¨obius band. Surfaces which have this property are said to be nonorientable; all other surfaces are orientable. The plane, the cylinder, the sphere, and the torus are examples of orientable surfaces