7 Drawings and Planar Graphs Respecting the fundamental nature of the Four colour problem in the development graph theory, it is only natural to study graph planarity, i.e., a possibility to draw a graph in the plane without edge crossings. This topic is quite close to classical geometry, too... Brief outline of this lecture • Plane drawings, rotations and faces, duality. Euler's formula. • Maximally plane graphs, edge bounds, and nonplanar graphs. • Characterization of planar graphs - the Theorem of Kuratowski. • Colouring planar maps and graphs - the Four Colour Problem. Petr Hliněný, Fl MU Brno, 2015 1/29 Fl: MA010: Drawings and planar graphs ^7.1 Defining a Planar Graph We would like to say what is a proper drawing of a graph in the plane, using points or "dots" for the vertices and non-crossing "nice lines" for the edges. However, what is a nice line? □ Definition: A simple continuous curve (shortly an arc) in the plane is the image of the interval [0,1] under a continuous simple map ip : [0,1] —> M2. tp(p) tp(l) ^(0) The points <£>(0), cp(l) are the ends of the arc, and the remaining points (the image of (0,1)) are called the interior of the arc. □ A simple closed continuous curve (shortly a loop) is defined in the same way except that it has one joint end cp(0) = <£>(!)■ v(o) = v(i) Note; an arc or a loop cannot "self-intersect", but otherwise they can look very "wild"! Though, we will see that it is enough to consider nicer polygonal arcs (Section 7.2). arc = obtouk^ toov = smycka, interior = vnithk^ Petr Hliněný, Fl MU Brno, 2015 2/29 Fl: MA010: Drawings and planar graphs Planar and plane graphs 1 Definition 7.1. A plane (multi)graph is a graph H = (V,E) represented such that - the vertex set V are distinct points in the plane, □ - every edge e = uv G E is an arc with the ends u,v (or loop) in the plane, and - the interior of every edge is disjoint from all other vertices and edges of H. □ A (multi)graph G is planar if G is isomorphic to some plane (multi)graph H. In such a situation we say that H is a plane drawing (or embedding) of the (multi)graph G. □ !!! Be aware of the difference; !!! T\ yt planar graph an abstract term □ plane graph an actual picture! Petr Hliněný, Fl MU Brno, 2015 pCcme graph = rovinní nakreslený graf, -plane drawing = rovinní nakreslení 3/29 Fl: MA010: Drawings and planar graphs Equivalence of plane drawings Obviously, isomorphic plane drawings (of the same graph) may look quite different. How much similar or different? • One plane drawing may be a "continuous deformation" of the other one (since the deformation happens in the sphere, one may turn a face "inside out"). □ • One may also be a "mirror image" of the other one. □ For these depicted kinds of deformation we do not care much, and we say that we have got equivalent (meaning "not much different") plane drawings of the same graph. continuous deformation = htadka deformace, mirror image = zrcadteni Petr Hlinený, Fl MU Brno, 2015 4/29 Fl: MA010: Drawings and planar graphs So, what else may be substantially different in two drawings of isomorphic graphs... ? • The two pictures, though being isomorphic as graphs, feature - different collections of "faces' (cf. a 4-face on the left, vs. a 5-face on the right),□ - and different "rotations' of edges around their vertices (at the same time). □ We aim to use the aforementioned features (faces and rotations) to distinguish between in-equivalent (meaning "very different") plane drawings of the same graph. Petr Hliněný, Fl MU Brno, 2015 5/29 Fl: MA010: Drawings and planar graphs ^Discrete Views of a Plane Drawing Rotation system Notation: For a graph G, let Ev C E(G) denote the set of edges incident with a vertex v G V(G). □ Definition: For a plane (multi)graph G, let II<3 = {71^ : v G V(G)} be a set of permutations, such that irv is the counterclockwise cyclic order of the set Ev in the drawing G. The set of permutations II is called the rotation system of the drawing G.n Definition: We say that two isomorphic plane (multi)graphs G and H are equivalent drawings if there exists an isomorphism from G to H which preserves their rotation systems, up to a possible mirror image (i.e., reversal of all the permutations). Notice that a "nice plane drawing" G clearly determines the rotation system (if a drawing is "not nice", then the rotation system is also well defined but one has to be careful with it... ).□ On the other hand, not every set of cyclic permutations {ttv : v G V(G)} corresponds to a plane drawing! rotation system = rotační system, equivalent drawings = ekyivatentninakjresteni Petr Hlinený, Fl MU Brno, 2015 6/29 Fl: MA010: Drawings and planar graphs For simplicity, we consider in this section only "nicely looking plane drawings", for which the following definitions of faces and facial walks make obvious sense. (Though, the definition of a face makes sense for any plane drawing, but that requires some nontrivial topological knowledge... See also Section 7.2.) □ Definition: Let G be a plane (multi)graph. The arcwise connected regions of the plane (including the outer one), separated by the drawing G are called the faces of G. • face 3 The boundary (or frontier) of each face of G forms a closed walk in the plane graph G which is called the facial walk (of the considered face). The length of this walk is called the size of the face. A facial walk is not always a cycle, see e.g., in the example above: the marked facial walk repeats one edge twice, and the face size is thus 8. □ Note that also the outer region of a plane drawing is considered as a face. arcwise connected'= obloukoví souvislý (spojený) face = stena, boundary = hranice, facial u>alk^= stenová-procházka Petr Hlinený, Fl MU Brno, 2015 7/29 Fl: MA010: Drawings and planar graphs Between rotations and facial walks Proposition 7.2. Two isomorphic plane (multi)graphsGi and G2 are equivalent drawings if, and only if, there exists an isomorphism between G\ and G2 which preserves all their facial walks. Proof: Let h : V{G\) —>> V{G2) be an isomorphism between G\ and G2. Assume that h does not preserve the rotation systems of G\ and G2, that is, there exists v G V{G\) such that the cyclic permutation ttv around v in G\ differs from 717^) in G2. nThen there exist edges e, e' G Ev which are consecutive in ttv but their images h(e), h(e') are not consecutive in ith{y)- This means that some facial walk through v in G\ contains both e,e' but no such facial walk exists in G2 containing both h{e\h{e'\ Thus, h does not preserve the facial walks. □ Conversely, assume that h preserves the rotation systems of G\ and G2. The proof will be finished if we show that a rotation system of G\ fully determines all the facial walks. The latter is easily shown from a picture... □ Petr Hliněný, Fl MU Brno, 2015 8/29 Fl: MA010: Drawings and planar graphs How many faces each of the drawings has? □ We can, e.g., construct the following alternative plane drawings—one by "flipping the tail" on the left and the other one by "moving the head" on the right. Why are these drawings not equivalent? This can be certified by the depicted facial walks. □ Concerning the number of faces, one can see that it is always 4, regardless of which drawing we choose—and this is not a coincidence as we will see in Theorem 7.10. □ Petr Hliněný, Fl MU Brno, 2015 9/29 Fl: MA010: Drawings and planar graphs ^Dual Plane Multigraphs For a plane graph G, consider the following construction: • Identify all the faces of G and place a new vertex into each face. • Join two of the new vertices by an edge iff the corresponding faces of G, resp. their facial walks, share an edge of G. For a formal definition of this concept, the incidence model of multigraphs is essential: Definition 7.4. The dual multigraph of a plane multigraph G = (V,E,e) is a multigraph H = (F, E, (j>) such that - F is the set of the faces of G, and □ - (f) is an incidence relation assigning (in H) to each edge e G E the two faces of G which have e on their boundary in G. In this situation, G is called the primal graph of dual H. dual multigraph = dudlni muttigraf Petr Hlinený, Fl MU Brno, 2015 10/29 Fl: MA010: Drawings and planar graphs Definition (repeated): For plane G = (V,E,e), the dual H = (F,E,(/)) is such that - F is the set of the faces of G, and - (f) is an incidence relation assigning (in H) to each edge e e E the two faces of G which have e on their boundary in G. Look carefully at the true meaning of Definition 7.4; • If the primal graph contains a vertex of degree 2, then in the dual graph, this results in a pair of parallel edges. □ • Likewise, a primal vertex of degree 1 gives a loop in the dual. □ Proposition 7.5. Two isomorphic plane multigraphs G\ and G2 3re equivalent drawings if, and only if, their dual multigraphs are isomorphic under the corresp. map.u Proof (a sketch): The isomorphism between the duals of G\ and G2 carries over to a one-to-one correspondence between the facial walks of G\ and those of a □ Petr Hliněný, Fl MU Brno, 2015 11 /29 Fl: MA010: Drawings and planar graphs Petr Hliněný, Fl MU Brno, 2015 12/29 Fl: MA010: Drawings and planar graphs 7.2 Plane Drawings and Euler's Formula In this section we turn the previous vague words about "nicely looking plane drawings" into a precise definition (which will help us to prove some of the coming claims). Definition: A polygonal arc is a finite sequence (po,pi,... ,Pk) ^ ^2 of points in the plane, together with the k straight line segments popi, P1P2, ■ ■ ■, Pk-iPk such that no two of them intersect (except at common ends). □ In a greater generality, the words polygonal arc refer also to the union of these line segments, and the points po,pk are the ends of this arc. □ Definition 7.6. A polygonal plane (multi)graph G (or a polygonal drawing of G) is a plane (multi)graph G such that all its edges are polygonal arcs. □ We give the following (topological) claim without a proof: Proposition 7.7. For every plane multigraph G, there exists an equivalent plane polygonal drawing of G. Pi We now review a few claims which can be declared as evident for polygonal plane drawings (while their truth for general plane drawings is much harder to establish). Fact: Let G be a polygonal plane multigraph. a) Every edge e G E(G) occurs either in two of the facial walks of G (once in each), or e is a bridge occuring twice in one of the facial walks. □ b) Likewise, if a vertex v repeats twice in a facial walk of G, then v is a cutvertex of Go c) Consequently, if G is 2-connected, then each of its facial walks is a graph cycle. Petr Hliněný, Fl MU Brno, 2015 14/29 Fl: MAOIO: Drawings and planar graphs ^"propo^tion^^ß divides the plane into precisely two regions. □ Proof (a sketch): Let P be the closed polygonal arc (as a point set in the plane). From every point x G M2 \ P, shoot a ray Rx to infinity, and count how many times Rx crosses P (just be careful at the corners of P which can be counted twice). □ - The parity of this number of crossings is an invariant of each of the regions; □ - hence, consequently, there are exactly two regions - the outer one with parity 0 and the inner one with parity 1. □ □ Proposition 7.9. Any polygonal plane drawing of a tree T has exactly one face. □ Proof (a sketch): One can follow a suitable BFS preorder on T to reach from any vertex (and from any incident face of it) to the "outside"; hence proving that there is only one arcwise connected region of R2 \ T. □ Petr Hliněný, Fl MU Brno, 2015 15/29 Fl: MAOIO: Drawings and planar graphs Euler's Formula Theorem 7.10. Let G be a (nonempty) connected polygonal plane multigraph with f faces. Then \V(G)\ + f-\E(G)\ = 2.u Proof: Let the number of vertices and of edges of G be n = |V(G)| and s = \E(G)\, respectively. We consider n fixed and apply induction on s. □ • Base: A minimal connected graph on n vertices is a tree with s = n — 1 edges, by Theorem 1.10. Then the number of faces is / = 1, by Proposition 7.9, and we get \V(G)\ + / - \E(G)\ = n + 1 - (n - 1) = 2 .□ • Induction step: We have that s > n and G is not a tree; hence there is a cycle C C G. Let e G E(C) be an arbitrary edge of the cycle. □ By Proposition 7.8, the two faces having e on their boundaries are distinct (note; C is not necessarily a face boundary). Hence, in the subgraph G\e, two former faces of G are merged into one and so G \ e has / — 1 faces and s — 1 edges. □ By the induction assumption for G\e\ \V{G \ e)\ + (/ - 1) - \E{G \ e)\ = n + (/ - 1) - (s - 1) = 2 , and so |V(G)| + / - \E(G)\ = n + /- s = n + (/-l)-(s-l)+ 1-1=2. □ * 'Euleruv vztah Petr Hlinený, Fl MU Brno, 2015 16/29 Fl: MA010: Drawings and planar graphs \V(G)\+f-\E(G)\=2 Notice that Euler's formula does not depend on a particular drawing of G. In other words, the number of faces is an invariant of an abstract planar graph (even though the faces themselves change from one drawing to another). □ Example 7.11. Find a connected simple plane graph with 6 vertices and 5 faces. It is now quite easy to see what the condition "5 faces" means... Though, from Euler's formula we get that the graph G in question should have \E{G)\ = \V(G)\ + /- 2 = 6 + 5- 2 = 9 edges.n Now it is much easier; we find, e.g., one of the following graphs: □ Petr Hliněný, Fl MU Brno, 2015 17/29 Fl: MA010: Drawings and planar graphs Recall that our proof of Euler's theorem (for polygonal drawings) makes use of two facts: - a closed polygonal arc divides the plane into precisely two regions, - a polygonal drawing of a tree has precisely one face. When formulated for general (i.e., non-polygonal) arc, these claims become higly nontrivial and they are commonly formulated as the famous old Jordan Curve Theorem which follows. □ Theorem 7.12. (Jordan Curve Theorem) A loop (non-self-intersecting continuous closed curve) in the plane divides the plane into precisely two regions. □ A proof of this important statement is far beyond the scope of our subject. Though, we can easily show that Theorem 7.12 is equivalent to the general statement of Euler's formula, for arbitrary (i.e., non-polygonal) plane graphs. Proposition 7.13. Theorem 7.12 holds true if, and only if, every connected plane graph with f faces satisfies \ V(G) \ + / - \E(G)\ = 2. Proof (a sketch): In the "if" dir., cons, the graph of a single vertex and a single loop edge—its drawing is a loop and the number of faces is / = \E(G)\ - \V(G)\ + 2 = 1-1 + 2 = 2. In the "only if" dir., repeat the proof of Theorem 7.10 while using Theorem 7.12. □ * Jordánova víta o íqnžnici Petr Hlinený, Fl MU Brno, 2015 18/29 Fl: MA010: Drawings and planar graphs ^7.3 Maximally Plane Graphs Remember the kids' game in which given dots are to be joined by as many as possible non-crossing arcs? This is the same as finding a maximal (by inclusion of edges) plane graph.□ Definition: A triangulation is a plane multigraph G (on > 3 vertices) such that each face of G (including the outer face) is bounded by a triangle of G. Note that a triangulation need not be a simple graph (possible parallel edges do not bound a common face). □ Example 7.14. IfG is a simple plane triangulation and \V(G)\ > 4, then 5(G) > 3. □ Assume, for a contradiction, that there is a vertex v £ V(G) of degree less than 3. Obviously, cIg(v) > 1, and so let u, w be the two neighbours of v in G. Then each of the two faces incident with v are bounded by walks (triangles) (u,uv,v,vw,w,e) and (u,uv,v,vw,w,e) where e, e are edges with ends u,w, and so e = e since G is simple. Hence, G itself is a triangle, a contradiction to IVYGOI > 4. □ trinaguiation = triangulate Petr Hliněný, Fl MU Brno, 2015 19/29 Fl: MA010: Drawings and planar graphs Theorem 7.15. A simple plane graph G on > 3 vertices is maximally plane, i.e., no edge e can be added to G to make a larger simple plane graph G + e if, and only if, G is a triangulation. □ (Be aware that this claim is not as evident as it might look at the first sight!) □ Proof: In the "if" direction, a triangulation G obviously cannot embed an additional edge without a crossing of edges (only possibilities are parallel to triangle edges). □ Conversely, assume that G has a face 0 of size (at least) 4. - If a vertex w is repeated in the facial walk of 0, then w is a cutvertex and so G is obviously not maximally plane. □ Hence 3 vertices has at most 3n — 6 edges. □ Proof: If G is a simple planar graph, then G has at most as many edges as a certain triangulation G+ D G on n vertices—the triangulation of Theorem 7.15. By Proposition 7.16, we have \E(G)\ < \E(G+)\ = 3n - 6. □ Petr Hliněný, Fl MU Brno, 2015 21/29 Fl: MA010: Drawings and planar graphs ^On some Non-planar Graphs We show how the previous findings about maximally planar graphs can be used to show that certain graphs are not planar (though, this is not a complete characterization yet). Example 7.18. Prove that the graphs K$ and are not planar. a) K$ has 5 vertices and 10 > 3 • 5 — 6 edges, a contradiction to Corollary 7.17. □ b) Concerning the graph K^^, the answer is not so easy since the bound 9 < 3-6 —6 = 12 holds true. However, note that is far from being a triangulation—it is actually triangle-free. □ Assume that had a plane drawing. Then the number of faces is 9 — 6 + 2 = 5 and each facial walk has at least 4 edges (no triangles at all), altogether > 5 • 4 = 20 occurrences of the edges of ^3,3. nSince every edge occurs twice in facial walks, that means Ks^ should have 20/2 = 10 > 9 edges, a contradiction. □ Petr Hliněný, Fl MU Brno, 2015 22/29 Fl: MA010: Drawings and planar graphs ^""Further"^ Proposition 7.19. A simple triangle-free planar graph on n > 3 vertices has at most 2n — 4 edges. □ Proof: Similarly as in the proof of Proposition 7.16, we estimate the number s of edges in triangle-free G. Every face is incident with at least 4 edges, and so s > \ • 4f and |e > /. iThen we continue with Theorem 7.10 (Euler's formula): 2 1 2 = n -\- j — s < n + —s — s = n--s 4 2 s < 2(n - 2) = 2n - 4. □ Corollary 7.20. Every simple planar graph contains a vertex of degree at most 5. Every simple triangle-free planar graph contains a vertex of degree at most 3. □ Proof: If all the vertex degrees in a simple n-vertex graph G are at least 6, then G has at least \ • 6n = 3n > 3n — 6 edges, and hence G is not planar, a contradiction. □ A similar contradiction holds in the second case. □ Petr Hliněný, Fl MU Brno, 2015 23/29 Fl: MA010: Drawings and planar graphs ^7.4 Planar Graph Characterizations The ultimate task in dealing with planarity is to characterize which graphs are planar, i.e., which graphs admit plane drawings—the theorem of Kuratowski. □ Definition: A subdivision of a graph G is obtained by replacing some edges of G by new paths of an arbitrary positive length. □ Theorem 7.21. (Kuratowski) A graph G is planar if, and only if, G contains no subdivisions of K$ or i^3)3 as subgraphs. □ Once again, we see an example of a good characterization: • The graphs K$ and K^,?, are clearly not planar (Example 7.18), and neither are their subdivisions which would actually have identical drawings. • An absence of any of the two obstructions already implies planarity, and one can find a plane drawing of the graph to provide a more obvious certificate. subdivision = podrozdefeni Petr Hlinený, Fl MU Brno, 2015 24/29 Fl: MA010: Drawings and planar graphs Example 7.22. Which of the following graphs are planar? Find the planar embeddings, or prove nonplanahty of the graph(s). Considering the two graphs for a while, we find out that A can be drawn as follows: x y —>> a The graph B, on the other hand, is not planar by Theorem 7.21 since it contains a subdivision of if3,3: □ Petr Hliněný, Fl MU Brno, 2015 25/29 Fl: MA010: Drawings and planar graphs ^""provingThe^^ We use another basic graph operation: contraction of an edge. A brief proof sketch: • <= If a graph G contains a subdivision of K$ or K^^, then G cannot be planar. • It is enough to prove the converse direction for 3-connected graphs (technical). • Claim. Every 3-connected graph G on at least 5 vertices contains an edge e such that contracting e in G leaves a 3-connected graph again. □ • Induction. Let 3-connected G contain no subdivision of K$ or and have at least 5 vertices. Denote by G' the 3-connected planar graph obtained by contracting the aforementioned edge e of G into a vertex w (of G'). □ The neighbours of w form a facial cycle Cw in G' \w, and we can examine all possible "uncontractions" (also called splittings) of w into e: - either the resulting G is again planar, or - we get a subdivision of K$ or i^3)3 induced on Cw + e. • The proof is finished. □ Petr Hliněný, Fl MU Brno, 2015 26/29 Fl: MA010: Drawings and planar graphs ^Uniqueness of Planar Drawings Every face of a 2-connected planar graph is enclosed by a cycle. Hence planar embed-dings of 2-connected graphs can be characterized by collections of their facial cycles.u Lemma 7.23. In any embedding of a 3-connected planar graph G, a cycle C is facial if and only if G \ V(C) is a connected subgraph. □ Proof: If G' = G\V(C) is connected, then whole G' is drawn in one face of C by the Jordan curve theorem. Conversely, assume C bounds a face of G, but G' has (at least) two components X and Y. Then the "attachement" vertices of X and Y on C are not overlapping, and hence X can be separated from Y in G by removing appropriate two vertices of C, contradicting 3-connectivity of G. □ □ Corollary 7.24. Every two planar embeddings of a 3-connected graph are equivalent (i.e. having the same collection of facial cycles). □ Moreover (without proofs) we have got: Theorem 7.25. Isomorphism testing of planar graphs can be done in linear time. □ Theorem 7.26. Every simple planar graph has a planar embedding such that the edges are straight line segments. uniqueness = jednoznačnost rovinného nakreslení Petr Hlinený, Fl MU Brno, 2015 27/29 Fl: MA010: Drawings and planar graphs ^7.5 Appendix: Colouring Maps and Planar Graphs Returning to the prime motivation of this lecture, the famous Four Colour Problem from the mid-19th century, we survey the following important solution; - proved first by Appel and Haken in 1976, □ - and then again by Robertson, Seymour, Sanders a Thomas in 1993. Theorem 7.27. Every loopless planar graph can be properly coloured with 4 colours.^ The proofs are, in the both cases, very complicated, and rely on a computer search. Vita o čtyřech barvách Petr Hlinený, Fl MU Brno, 2015 28/29 Fl: MA010: Drawings and planar graphs Some easier (and weaker) cases Given great difficulty of the Four Colour Problem solution, here we only sketch two simpler and weaker claims following from Corollary 7.20. Proposition 7.28. Every loopless planar graph is ^-colourable. Every loopless triangle-free planar graph is ^-colourable. □ Moreover, the following generalized result has an exceptionally beautiful proof: Theorem 7.29. Every loopless planar graph has the list chromatic number at most 5.n Proof (sketch): The following can be proved by a straightforward induction. Let a plane graph G have the outer face bounded by a cycle G, and all other faces be triangles. Assume that every vertex ofG except those ofC are assigned lists of 5 colours, some two neighbouring vertices of G have preselected distinct colours, and the rest of the vertices of C are assigned lists of 3 colours. Then there is a proper list colouring of G. Recall Definition 6.23 of list colourings. □