27510.6Surfacmbeddings of Graphsk vertices. The graph obtained from their union G, UG2 by deleting the edges ofGi nG2 is called the k-sum of Gi and G2.a) Show that if Gi and G2 are planar and k = 0,1, or 2, then the k-sum of GandG2isalsoplanab) Express the nonplanar graph K3,3 as a 3-sum of two planar graphs.10.5.11SERIES-PARALLELGRAPHA series ertension of a graph is the subdivision of a link of the graph; a parallelertension is the addition of a new link joining two adjacent vertices. A series.parallel graph is one that can be obtained from K2 by a sequence of series andparallel extensionsa) Show that a series-parallel graph has no Kf-minor.b)By applying Exercise 10.1.5, deduce that a graph has no Ky-minor if and onlyif it can be obtained from Ki, the loop graph L, (a loop incident with a singlevertex), and the family of series-parallel graphs, by means of O-sums, I-sums(G.A. DIRAC)and2-sums10.5.12 Show that agraph is outerplanar if and only ifit has neithera Ka-minornoraK2.3-mino10.5.13 ExCLUDEDK3.3-MINORShowthata) every 3-connected nonplanar graph on six or more vertices has a Kaa-minorb) any graph with no K3.37edfromthefamilyofplanargraphsmTbeobtaand K, by means of O-sums, 1-sums, and 2-sums. (D.W. HALL; K. WAGNER)10.5.14 ExCLUDED Ks-MINORShowthata) the Wagner graph, depicted in Figure 10.23, has no Kg-minor,b)if Gi and G2 aretwo graphs,each of which is either a planar graph or theWagner graph, then no O-sum, 1-sum, 2-sum, or 3-sum of Gi and G2 has aKs-minor(Wagner (1936) showed that every 4-connected nonplanar graph has a Ks-minorand deduced the converse of (b), namely that any graph with no Kg-minor canbe obtained from the family of planar graphs and the Wagner graph by means of0-sums, 1-sums, 2-sums, and 3-sums.)10.6 Surface Embeddings of GraphsDuring the nineteenth century, in their attempts to discover generalizations ofEuler's Formula (10.2) and the Four-Colour Conjecture (discussed in the nextchapter),graph theorists were led to the study of embeddings of graphs on surfaces
10.6 Surface Embeddings of Graphs 275 k vertices. The graph obtained from their union G1 ∪ G2 by deleting the edges of G1 ∩ G2 is called the k-sum of G1 and G2. a) Show that if G1 and G2 are planar and k = 0, 1, or 2, then the k-sum of G1 and G2 is also planar. b) Express the nonplanar graph K3,3 as a 3-sum of two planar graphs. 10.5.11 Series-Parallel Graph A series extension of a graph is the subdivision of a link of the graph; a parallel extension is the addition of a new link joining two adjacent vertices. A seriesparallel graph is one that can be obtained from K2 by a sequence of series and parallel extensions. a) Show that a series-parallel graph has no K4-minor. b) By applying Exercise 10.1.5, deduce that a graph has no K4-minor if and only if it can be obtained from K1, the loop graph L1 (a loop incident with a single vertex), and the family of series-parallel graphs, by means of 0-sums, 1-sums, and 2-sums. (G.A. Dirac) 10.5.12 Show that a graph is outerplanar if and only if it has neither a K4-minor nor a K2,3-minor. 10.5.13 Excluded K3,3-Minor Show that: a) every 3-connected nonplanar graph on six or more vertices has a K3,3-minor, b) any graph with no K3,3-minor can be obtained from the family of planar graphs and K5 by means of 0-sums, 1-sums, and 2-sums. (D.W. Hall; K. Wagner) 10.5.14 Excluded K5-Minor Show that: a) the Wagner graph, depicted in Figure 10.23, has no K5-minor, b) if G1 and G2 are two graphs, each of which is either a planar graph or the Wagner graph, then no 0-sum, 1-sum, 2-sum, or 3-sum of G1 and G2 has a K5-minor. (Wagner (1936) showed that every 4-connected nonplanar graph has a K5-minor and deduced the converse of (b), namely that any graph with no K5-minor can be obtained from the family of planar graphs and the Wagner graph by means of 0-sums, 1-sums, 2-sums, and 3-sums.) 10.6 Surface Embeddings of Graphs During the nineteenth century, in their attempts to discover generalizations of Euler’s Formula (10.2) and the Four-Colour Conjecture (discussed in the next chapter), graph theorists were led to the study of embeddings of graphs on surfaces
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 surfaces
276 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 treewidth, 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
2770.lingsofGraphs(a)(6)Fig. 10.24. (a) The Mobius band, and (b) the torusA surface is closed if it is bounded but has no boundary.The Mobius band hasa boundary which is homeeomorphic (that is, continuously deformable) to a circleand, hence, is not a closed surface.The plane is clearly not bounded, hence isnot a closed surface either.The simplest closed surface is the sphere. Other closedsurfaces are sometimes referred to as higher surfaces. Starting with the sphere, allhigher surfaces can be constructed by means of two operations.Let S be a sphere.let D, and D2be two disjoint discs of egual radius onS.and let H becylinder of these radius as Dr and D2.The operation ofaddingahandletoSatDiand Daconsists of cutting out Dr and Dafromsand thenbending and attaching H to S in such a way that tl01im of oneof theends of H coirwiththendary of Dr and the rim of the other end of Hcoincides with thebdary of D,Any number of disjoint handles may be addedto S by selecting disjoint pairs of discs on S and adding a handle at each of thosepairs of discs. A sphere with k handles is the surface obtained from a sphere byadding k handles; it is denoted by Sk, and the index k is its genus. The torus ishomeomorphic to a sphere with one handle, Si. More generally, every orientablesurfaceishomeomorphictoa spherewithkhandlesforsomek>0Asmentioned above (see also Section3.5),givenanyrectangleABCDomay obtain a torus by identifying the side AB with the side DC and the side ADwith the side BC. Moreenerally, any orientable surfacemay be constructed froma suitable polygon by identifying its sides in a specified maer.Forexamplethe surface S2, also known as the double torus, may be obtained by a suitableidentification of the sides of an octagon (see Exercise 10.6.2)We now turn to nonorientable surfaces. Let S be a sphere, let D be a disc on S.and let B be a Mobius band whose boundary has the same length as the circumferenceof D.Theoperationof adding across-captoSatD consistsofattachingBtoS so that the boundaries of D and B coincide.Equivalently,this operation consistsof sewing' or identifying' every point on the boundary of D to the point of D thatis antipodal toit.Just as with handles, we may attach annumber of cross-capsto a sphere. The surface obtained from the sphere by attaching one cross-capis
10.6 Surface Embeddings of Graphs 277 (a) (b) Fig. 10.24. (a) The M¨obius band, and (b) the torus A surface is closed if it is bounded but has no boundary. The M¨obius band has a boundary which is homeomorphic (that is, continuously deformable) to a circle and, hence, is not a closed surface. The plane is clearly not bounded, hence is not a closed surface either. The simplest closed surface is the sphere. Other closed surfaces are sometimes referred to as higher surfaces. Starting with the sphere, all higher surfaces can be constructed by means of two operations. Let S be a sphere, let D1 and D2 be two disjoint discs of equal radius on S, and let H be a cylinder of the same radius as D1 and D2. The operation of adding a handle to S at D1 and D2 consists of cutting out D1 and D2 from S and then bending and attaching H to S in such a way that the rim of one of the ends of H coincides with the boundary of D1 and the rim of the other end of H coincides with the boundary of D2. Any number of disjoint handles may be added to S by selecting disjoint pairs of discs on S and adding a handle at each of those pairs of discs. A sphere with k handles is the surface obtained from a sphere by adding k handles; it is denoted by Sk, and the index k is its genus. The torus is homeomorphic to a sphere with one handle, S1. More generally, every orientable surface is homeomorphic to a sphere with k handles for some k ≥ 0. As mentioned above (see also Section 3.5), given any rectangle ABCD, one may obtain a torus by identifying the side AB with the side DC and the side AD with the side BC. More generally, any orientable surface may be constructed from a suitable polygon by identifying its sides in a specified manner. For example, the surface S2, also known as the double torus, may be obtained by a suitable identification of the sides of an octagon (see Exercise 10.6.2). We now turn to nonorientable surfaces. Let S be a sphere, let D be a disc on S, and let B be a M¨obius band whose boundary has the same length as the circumference of D. The operation of adding a cross-cap to S at D consists of attaching B to S so that the boundaries of D and B coincide. Equivalently, this operation consists of ‘sewing’ or ‘identifying’ every point on the boundary of D to the point of D that is antipodal to it. Just as with handles, we may attach any number of cross-caps to a sphere. The surface obtained from the sphere by attaching one cross-cap is
27810 PlanarGraphsknownastheprojectiveplanendistheslestnonorientablesurface.Aspherewithkcross-caps isdenotedbyN,theindexbeing its cross-capnumber.Everyclosed nonorientable surface is homeomorphic to N, for some k ≥1As with orientableclosed surfaces,allnonorientableclosed surfacesmayberepresented bypolvgons,along with indications as to how their sides are to beidentified (although it is not possible to obtain phvsical models of these surfacesin this way).The projective polaneforextample,mayberepresented byarectangleABCDihtiABisidfiedwiththesideCD(sothatAcoincidewith C and B with D) and the side AD is identified with the side CB. Equivalentlymay be represented by a disc in which every point on thetheprojectiveplanboundary is identified with its antipodal point.Aniportant theorem of the topology of surfaces, known as the classificationtheorem for surfaces, states that every closed surface is homeomorphic to eitherSkorNk,forasuitablevalueofk.Onemay,of course,obtainsurfacesbyaddingboth handles and cropsto spheres.However,onedoesnot produceanynewsurfaces in this way. It turns out that the surface obtained from the sphere byadding k > 0 handles and e > 0 cross-caps is homeormorphic to N2k+e.In Chapter 3, we presented embeddings of K, and the Petergraphotorus (see Figure 3.9). Embeddings of K and the Petersen graph on the projectiveplane are shown in Figure 10.25.(6)(a)Fig.10.25. Embeddings on the projective plane of (a) K6, and (b) the Petersen graphPolygonal representations of surfaces are convenient for displaying embeddingsof graphs on surfaces of low genus or cross-cap number. However,for more complicated surfaces, such representations are unwieldy. Convenient algebraic and combinatorial schemes exist for describing embeddings on arbitrary surfaces.THE EULER CHARACTERISTICAn embedding G of a graph G on a surface is a cellular embedding if each ofthe arcwise-coonnected regions of |G is homeomorphic to the open disc. Theseregions are the faces of G, and their number is denoted by f(G)
278 10 Planar Graphs known as the projective plane and is the simplest nonorientable surface. A sphere with k cross-caps is denoted by Nk, the index k being its cross-cap number. Every closed nonorientable surface is homeomorphic to Nk for some k ≥ 1. As with orientable closed surfaces, all nonorientable closed surfaces may be represented by polygons, along with indications as to how their sides are to be identified (although it is not possible to obtain physical models of these surfaces in this way). The projective plane, for example, may be represented by a rectangle ABCD in which the side AB is identified with the side CD (so that A coincides with C and B with D) and the side AD is identified with the side CB. Equivalently, the projective plane may be represented by a disc in which every point on the boundary is identified with its antipodal point. An important theorem of the topology of surfaces, known as the classification theorem for surfaces, states that every closed surface is homeomorphic to either Sk or Nk, for a suitable value of k. One may, of course, obtain surfaces by adding both handles and cross-caps to spheres. However, one does not produce any new surfaces in this way. It turns out that the surface obtained from the sphere by adding k > 0 handles and > 0 cross-caps is homeomorphic to N2k+. In Chapter 3, we presented embeddings of K7 and the Petersen graph on the torus (see Figure 3.9). Embeddings of K6 and the Petersen graph on the projective plane are shown in Figure 10.25. (a) (b) Fig. 10.25. Embeddings on the projective plane of (a) K6, and (b) the Petersen graph Polygonal representations of surfaces are convenient for displaying embeddings of graphs on surfaces of low genus or cross-cap number. However, for more complicated surfaces, such representations are unwieldy. Convenient algebraic and combinatorial schemes exist for describing embeddings on arbitrary surfaces. The Euler Characteristic An embedding G of a graph G on a surface Σ is a cellular embedding if each of the arcwise-connected regions of Σ \ G is homeomorphic to the open disc. These regions are the faces of G, and their number is denoted by f(G)
10.6 Surface Embeddings of Graphs279Consider, for example, the two embeddings of Ky on the torus shown in Figure 10.26.The first ernbedding is cellular:ithas twofaces,bounded bythe closedwalks 12341 and 124134231, respectively. The second embedding is not cellularbecause one of its faces is homeomorphic to a cylinder, bounded by the cycles 1231and1431(a)(6)Fig.10.26.Twoembeddings of Konthetorus:(a)acellulalrembedding,and (b) anoncellular embeddingMost theorems of interest about embeddings are valid only for cellular embeddings. For this reason, all the embeddings that we discuss are assumed to becellularThe Euler characteristic of a surface , denoted c(), is defined by:2-2kifishomeomorphictoSc(2) :=2-kifZishomeomorphictoNThus the Euler characteristics of the sphere, the projective plane, and the torusare 2,,and 0,respectively.Thefollowing theoremisageneralization of EulerFormula (10.2) for graphs embedded on surfacesTheorem 10.37 Let G be an embedding of a connected graph G on a surface .Then:(G) - e(G) + f(G) = c(2)口The following easy corollaries of Theorem 10.37 generalize Corollaries 10.20and 10.21 to higher surfaces (Exercise 10.6.3)Corollary 10.38 Allembeddings of a connected graph on a given surface have th-same number offaces.Corollary 10.39 Let G be a simple connected graph that is embeddable on a surface .Then口m≤3(n=c(2)
10.6 Surface Embeddings of Graphs 279 Consider, for example, the two embeddings of K4 on the torus shown in Figure 10.26. The first embedding is cellular: it has two faces, bounded by the closed walks 12341 and 124134231, respectively. The second embedding is not cellular, because one of its faces is homeomorphic to a cylinder, bounded by the cycles 1231 and 1431. (a) (b) 1 1 2 2 3 3 4 4 Fig. 10.26. Two embeddings of K4 on the torus: (a) a cellular embedding, and (b) a noncellular embedding Most theorems of interest about embeddings are valid only for cellular embeddings. For this reason, all the embeddings that we discuss are assumed to be cellular. The Euler characteristic of a surface Σ, denoted c(Σ), is defined by: c(Σ) := 2 − 2k if Σ is homeomorphic to Sk 2 − k if Σ is homeomorphic to Nk Thus the Euler characteristics of the sphere, the projective plane, and the torus are 2, 1, and 0, respectively. The following theorem is a generalization of Euler’s Formula (10.2) for graphs embedded on surfaces. Theorem 10.37 Let G be an embedding of a connected graph G on a surface Σ. Then: v(G) − e(G) + f(G) = c(Σ) The following easy corollaries of Theorem 10.37 generalize Corollaries 10.20 and 10.21 to higher surfaces (Exercise 10.6.3). Corollary 10.38 All embeddings of a connected graph on a given surface have the same number of faces. Corollary 10.39 Let G be a simple connected graph that is embeddable on a surface Σ. Then m ≤ 3(n−c(Σ))