Graph theory · Definition
Planar graph
Before you start you need to know
Planarity answers when a network (circuits, maps, roads) can be laid out on a sheet of paper with no connections crossing.
Definition
A planar graph is a graph that can be drawn in the plane with no crossing edges; such a drawing, for \(v\) vertices and \(e\) edges, splits the plane into \(f\) faces.
Planar does not mean that every drawing of the graph is free of crossings, only that at least one exists. The same graph can be drawn with crossings and still be planar if it is redrawn. Once a crossing-free drawing is fixed, the edges split the plane into regions called faces; the infinite region surrounding everything counts as one more face, the outer one.
The central result is Euler's formula: in a plane drawing of a connected graph, \(v-e+f=2\). For a graph with \(c\) connected components it becomes \(v-e+f=1+c\). From it follows that a simple planar graph with \(v\ge3\) satisfies \(e\le 3v-6\), because every face is bounded by at least three edges and every edge borders two faces. If there are also no triangles, every face has at least four edges and then \(e\le 2v-4\).
These bounds let us prove that a graph is not planar: \(K_5\) has 10 edges and \(3\cdot5-6=9\), and \(K_{3,3}\) has 9 edges and \(2\cdot6-4=8\). Beware of the converse: meeting the bound does not guarantee planarity, as \(K_{3,3}\) against \(3v-6=12\) shows. Kuratowski's theorem completes the picture: a graph is planar exactly when it contains no subdivision of \(K_5\) or \(K_{3,3}\). The classic puzzle of three houses and three utilities is precisely \(K_{3,3}\).
Think about it
A tree with \(v\) vertices has \(e=v-1\) edges. How many faces does it have when drawn in the plane?
Just one, the outer face: \(f=2-v+(v-1)=1\). With no cycles no region is enclosed.
Is the cycle graph \(C_n\) planar? How many faces does it have?
Yes: it is a polygon. It has \(n\) vertices, \(n\) edges and \(f=2-n+n=2\) faces, the inner and the outer one.
Exercises 10
- Which of the following complete graphs is planar?
- A connected planar graph has \(v=8\) vertices and \(e=12\) edges. How many faces (counting the outer one) does its drawing have?
- A plane drawing of a connected graph has 6 vertices and 5 faces. How many edges does it have?
- A simple, connected, planar graph has \(v=7\) vertices. What is the largest possible number of edges?
- Why is \(K_5\) not planar?
- A tree with 10 vertices is drawn in the plane. How many faces does the drawing have?
- A planar graph, not necessarily connected, has 2 connected components, \(v=9\) vertices and \(e=10\) edges. If \(v-e+f=1+c\) with \(c\) components, how many faces does its drawing have?
- A connected planar graph with no triangles satisfies \(e\le 2v-4\). Is \(K_{3,3}\) (6 vertices, 9 edges, no triangles) planar?
- A maximal planar graph with \(v=10\) vertices (every face a triangle) has \(e=24\) edges. How many faces does it have?
- Which statement is true?
References
- Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.7
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.5