Class Five: Embeddings - Columbia University

1 Class five : EmbeddingsK3,3K5It many applications of graph theory it is important to determine how onecan draw a particular graph with as few edges overlapping as possible. Forexample, consider the problem of designing a microchip or building a subwaysystem, overlapping edges here either lead to disfunction or are very graphis a graph which can be drawn in the plane without anyedges crossing. We refer to a specific drawing of a graph as numberof a graph is the smallest possible numberof edge crossings when considering all possible drawings of the graph. Hence,agraphisplanarifandonlyifithascros singnumberzero. Belowaretwodi erent Embeddings of the complete graph on four vertices, one with cross-ing number one and one with crossing number zero. Note, this shows thatcomplete graph on four vertices is indeed a planar graph.

2 When a graph isdrawn with no crossing edges, it divides the plane into a set of regions, whichwe callfacesand denote Curve theorem. For example, the planar embedding below results infour regions/faces, that is,f= some small graphs and think about the following questions:Draw regular planar graphs of degreed=0,1,2,3,4, happens when you delete a vertex from a planar graph?What happens when you delete an edge from a planar graph?Are all graphs planar? In particular, is the complete graph on 5 vertices planar?What is the crossing number of the complete graph on five vertices?What about the complete graph on five vertices minus an edge?What is the crossing number of the complete graph on six vertices?How about seven vertices?Consider a cycle with some additional chordal is such a graph not planar?

3 Try and make as small an example as planarif the addition of one more edgeyields a non-planar does a face of a maximal planar graph look like?How many edges and faces, does a connected maximal planar graph have?If a graph is planar, is there a planar embedding in which every edge is a straight line segment?How many faces does a cycle have?How many faces does a path have?How many faces does a tree have?If two planar graphs have the same number of vertices, edges and faces,need they be isomorphic?What about two planar graphs with the same degree sequence and number of faces?For several planar graphs determine the number of di erent Embeddings yield a di erent number of faces?Do you notice a pattern?Is the Petersen graph drawn below planar? complete graph on 5 vertices is non-planar, yet deleting anyedge yields a planar (Guy s Conjecture).

4 Cr(Kn)=14bn2cbn 12cbn 22cbn (F ary, Wagner).Every planar graph has a planar embedding inwhich every edge is a straight line planar graph is a tangency graph of circles in the (Jordan Curve Theorem).Any continuous simple closed curve inthe plane, separates the plane into two disjoint regions, the inside and (Euler).IfGis a connected planar graph onvvertices witheedgesandffaces, thenv e+f= complete bipartite graphK3,3is non-planar, yet deleting anyedge yields a planar (Kuratowski).A graph is planar if and only if it contains no sub-division ofK3, Euler s formula give an upper bound for the number of edges ina connected planar graph on at least three Euler s formula give an upper bound for the number of edges following two results show that bothK5andK3,3are a connected planar graph on at least three vertices, then|E(G)| 3|V(G)| a connected planar graph on at least three vertices that con-tains no triangles, then|E(G)| 2|V(G)| question of whether one is able to draw a graph without crossing edgescan be asked with respect to other the following graphs on the surface of a donut (torus)

5 Without crossing complete bipartite graphK3, complete complete graphK6 The complete dealing with the embedding question on the torus, there is indeed aresult analogous to Kuratowski for the plane, however instead of two minimalexamples there are thousands. The complete graph on 8 verticesK8is one ofthem. Also on the torusv e+f= graphis a planar graph such that all vertices have degreedand all faces have the same number of bounding edgesbwhere bothd,b include the tetrahedron and cube graphs drawn below. This mirrorsEuclidean geometry. It was know to the Greeks that there were exactly fiveplatonic solids, that is, convex polyhedron with congruent faces of regularpolygons such that the same number of faces meeting at each each vertex has degreed,thehandshakinglemmaimpliesthatdv = ,thehandshakinglemmaimpliesthatbf= ,v=2edandf=2eb.

6 And so plugging intov e+f=2yieldsthat2ed+2eb=2+e> +1b> are only five possible solutions each of which corresponds uniquely to aplatonic solid: d=b=3 !Tetrahedron. d=3andb=4 !Cube. d=4andb=3 !Octahedron. d=3andb=5 !Dodecahedron. d=5andb=3 !Icosahedron.