*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, 2014
Fl: MA010: Drawings and planar graphs
7.1   Defining a Planar Graph
We would like to draw graphs (in the plane) using points ("dots") for the vertices and 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.
The points ip(0),ip(l) are the ends of the arc, and the remaining points (the image '■f((0,1))) are called the interior of the arc. □
A simple closed continuous curve (shortly a loop) is defined in the same way as an arc except that it has one joint end tp(0) — if (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 = oUCoukj Coop = smyčka, interior = vnitřek..
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Planar and plane graphs
Definition 7.1. A plane (multi)graph is a graph G — (V,E) represented such that
- the vertex set V are distinct points in the plane, □
- every edge e — uv e 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 G. □
A (multi)graph G is planar if G is isomorphic to some plane (multi)graph H. In such a situation we say that if is a plane drawing (or embedding) of the (multi)graph G. □
!!! Be aware of the difference; Ml T\ /f
planar graph an abstract term
□
plane graph an actual picture!
Petr Hliněný,   Fl MU Brno, 2014
píone graph = rovinně naíq;estemjgraf, píane drawing = rovinné nafcrestmi
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.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Equivalence of plane drawings, II
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, 2014
Fl: MA010: Drawings and planar graphs
Discrete Views of a Plane Drawing
Rotation system
Notation: For a graph G, let EVC. E(G) denote the set of edges incident with a vertex v e V(G). □
Definition: For a plane (multi)graph G, let Ha — {ttv ■ v e V(G)} be the 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.o
Definition: We say that two isomorphic plane (multi)graphs G and H are equivalent drawings if there exists an isomorphism (between them) which preserves their rotation systems, up to (possibly) a mirror image.
Note that a "nice plane drawing" G uniquely 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 e V(G)} corresponds to a plane drawing!
rotation system = rotační systém, equivalent drawings = ekvivahntni nal^resCeni, mirror = zrcacttouý
Petr Hlinený,   Fl MU Brno,  2014 6/33 Fl: MA010: Drawings and planar graphs
Facial walks
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 adge twice, and the face size is thus 8. □
Note that also the outer region of a plane drawing is considered as a face.
arczoise connecte£= oúloukgvěsouvislý (spojený) face = sténá, Boundary = Hranice, facialzúaík. = stěnová procházka
Petr Hlinený,   Fl MU Brno,  2014 7/33 Fl: MA010: Drawings and planar graphs
Between rotations and facial walks
Proposition 7.2. Two isomorphic plane (multi)graphs Gi and G2 are equivalent drawings if, and only if, there exists an isomorphism between G\ and Gi which preserves all their facial walks.
Petr Hliněný.   Fl MU Brno. 2014
_
Fl: MA010: Drawings and planar graphs
Example 7.3. Find two other (at least), non-equivalent plane drawings of the following graph:
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, 2014
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, <f>) such that
- F is the set of the faces of G, and □
- 0 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.
Petr Hlinený,   Fl ML) Brno,   2014 10/33 Fl: MA010: Drawings and planar graphs
Definition (repeated): For plane G — (V, E, e), dual H — (F, E, <f>) is such that
- F is the set of the faces of G, and
- 0 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.
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 are equivalent drawings if, and only if, their dual multigraphs are isomorphic under the corresp. map.a
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 G2. C
□
Petr Hliněný,   Fl MU Brno, 2014
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) C M2 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
votiiaonaC arc = Comma čára
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Assorted claims about plane drawings
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 Gfa
c) Consequently, if G is 2-connected, then each of its facial walks is a graph cycle.
<
>
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Drawings and planar graphs
Proposition 7.8. Every closed polygonal arc (non-self-intersecting by the definition!) 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 iel2\P, shoot a ray Rx (to infinity), and count how many times Rx crosses P (just be careful at corners of P). □
- 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 M2 \ T. C
Petr Hliněný,   Fl MU Brno, 2014
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)\ + f- \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\f)\ + (f-l)-\E(G\f)\=n+(f-l)-(s-l)= 2, and so \V(G)\ + f - \E(G)\ = n + f - s = n+ (f - 1) - (s - 1) + 1 - 1 = 2. C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Using Euler's formula
\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)\ + f -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, 2014
Fl: MA010: Drawings and planar graphs
Remark: the Jordan Curve Theorem
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. C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: 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 trinagulation need not be a simple graph (possible parallel edges do not bound a common face). □
Example 7.14. If G is a simple plane triangulation and \ V(G) \ > 4, then 5(G) > 3.
Assume, for a contradiction, that there is a vertex v e V(G) of degree less than 3. Obviously, da(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 IV(G)I > 4. □
trinagulation = trianguLace
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Triangulations as maximally plane 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 <f> of size (at least) 4.
- If a vertex w is repeated in the facial walk of <f>, then w is a cutvertex and so G is obviously not maximally plane. □
Hence <f> has four vertices wi,W2,W3,W4 in this cyclic order on the boundary.
- Then each of the edges W1W3 and W2W4 must exist in G, since otherwise one of them could be added to G, contradicting the max.-plane property of G. □
- However, the edges W1W3 and W2W4 then cross in G, contr. planarity. □
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Number of edges in a triangulation
So, how many edges can one draw in a (maximal) plane graph on a given number n of vertices? Is this number indepenent of the particular drawing(s)? Actually, yes... □
Proposition 7.16. A polygonal plane triangulation G on n vert, has prec. 3n—6 edges.
Proof: Let s be the number of edges of G and / be the number of faces. Since G is a triangulation, every facial walk of G has three edges, and each edge of G occurs in these walks exactly twice. Consequently, 2s — 3/ and we conclude from Theorem 7.10
2 1
2 — n + f — s — n + —s — s — n — —s o o
s = \E(G)\ = 3(n - 2) = 3n - 6 .□
C
Corollary 7.17. A simple plane graph on n > 3 vertices has at most 3n — 6 edges. □
Proof: If G is a simple plane graph, then G has at most as many edges as a certain triangulation G+ DGonn vertices—the triangulation of Theorem 7.15.
By Proposition 7.16, we have \E(G)\ < \E(G+)\ = 3n - 6. C
Petr Hliněný,   Fl MU Brno, 2014
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 -^3,3, the answer is not so easy since the bound 9 < 3-6 — 6 = 12 holds true. However, note that ^33 is far from being a triangulation—it is actually triangle-free. □
Assume that ^33 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 K33 should have 20/2 — 10 > 9 edges, a contradiction. C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Further bounds on the number of edges
Corollary 7.19. A simple triangle-free planar graph on n > 3 vertices has < 2n — 4 edges. □
Proof: Since G has now no triangles, every face is incident with at least 4 edges. Then e > \ ■ 4/, and |e > /. From Theorem 8.2 we get
2 1
2 — n + f — e < n-\—e — e — n--e
4 2
e < 2(n-2) = 2n-4.n
Petr Hliněný,   Fl MU Brno, 2014
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.20. (Kuratowski)   A graph G is planar if, and only if, G contains no subdivisions of K$ or        as subgraphs. □
Once again, we see an example of a good characterization:
• The graphs K5 and Kz,z 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 = podrozdeleni
Petr Hlinený,   Fl ML) Brno,   2014 23/33 Fl: MA010: Drawings and planar graphs
Example 7.21. Which of the following graphs are planar? Find the planar embeddings, or prove nonplanarity of the graph(s).
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Proving the Kuratowski theorem
Petr Hliněný,   Fl MU Brno, 2014
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.22. 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. □ C
Corollary 7.23. 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.24. Isomorphism testing of planar graphs can be done in linear time. □
Theorem 7.25. Every simple planar graph has a planar embedding such that the edges are straight line segments.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
7.5   Appendix: Colouring Maps and Planar Graphs
Returning to the motivation of this lecture, we survey the following important result;
- proved first by Appel and Haken in 1976,
- and then again by Robertson, Seymour, Sanders a Thomas in 1993.
Theorem 7.26. Every loopless planar graph can be properly coloured with 4 colours, a The proofs are, in both cases, very complicated, and rely on a computer search.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs
Easier (and weaker) cases
Hence we sketch here some simpler and weaker statements following from Corollary 8.4.
Proposition 7.27. Every loopless planar graph is ^-colourable. Every loopless triangle-free planar graph is ^-colourable. □
Moreover, the following generalized result has exceptionally beautiful proof: Theorem 7.28. Every loopless planar graph has the list chromatic number at most 5.n
Proof (sketch): The following is proved by a straightforward induction.
Let a planar embedded graph G have the outer face bounded by a cycle C, and all other faces be triangles. Assume every vertex ofG except those of C are assigned lists of 5 colours, some two neighbouring vertices of C 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. [-
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Drawings and planar graphs