# Chapter 36. Planar Graphs # Chapter 36. Planar Graphs A graph is planar when it can be drawn in the plane so that edges meet only at common endpoints. Such a drawing is called a planar embedding or a plane drawing. The important point is that planarity is a property of the graph, not of a particular drawing. A graph may be drawn with crossings and still be planar, provided another drawing removes those crossings. ## 36.1 Planar Drawings Let \(G = (V,E)\) be a graph. A drawing of \(G\) assigns each vertex to a point in the plane and each edge to a curve joining the points assigned to its endpoints. A drawing is planar if no two edges cross except at a shared endpoint. A graph is planar if it has at least one planar drawing. For example, a triangle is planar. A square with both diagonals drawn has a crossing in the usual picture, but the graph \(K_4\) is planar because it can be redrawn without crossings. By contrast, \(K_5\) and \(K_{3,3}\) are the classical nonplanar examples. ## 36.2 Plane Graphs A planar graph is an abstract graph that admits a crossing-free drawing. A plane graph is a planar graph together with a fixed crossing-free drawing. This distinction matters. The same planar graph may have different embeddings. In each embedding, the edges divide the plane into connected regions called faces. One face is unbounded and is called the outer face. Thus a plane graph has vertices, edges, and faces. The faces belong to the embedding, while the vertices and edges belong to the graph. ## 36.3 Faces A face is a connected region of the plane left after removing the drawing of the graph. The unbounded region is counted as a face. For a cycle \(C_n\), the plane is divided into two faces: the inside of the cycle and the outside of the cycle. For a tree, there is only one face. Since a tree has no cycle, its drawing does not enclose a bounded region. Faces are not just visual objects. They are part of the combinatorial structure of a plane graph. Euler's formula relates the number of vertices, edges, and faces in every connected plane graph. ## 36.4 Euler's Formula Let \(G\) be a connected plane graph. Let $$ v = |V|, \qquad e = |E|, \qquad f = \text{number of faces}. $$ Then $$ v - e + f = 2. $$ This is Euler's formula for connected planar graphs. It is one of the basic theorems of planar graph theory. ### Example A triangle has $$ v = 3, \qquad e = 3, \qquad f = 2. $$ Hence $$ v - e + f = 3 - 3 + 2 = 2. $$ A square with one diagonal has $$ v = 4, \qquad e = 5, \qquad f = 3. $$ Hence $$ v - e + f = 4 - 5 + 3 = 2. $$ ## 36.5 Consequences of Euler's Formula Euler's formula implies that planar graphs are sparse. A simple connected planar graph with at least three vertices satisfies $$ e \leq 3v - 6. $$ To see why, suppose every face is bounded by at least three edges. Counting edge appearances along face boundaries gives $$ 3f \leq 2e, $$ because each edge is incident with at most two faces. Combining this inequality with Euler's formula gives $$ v - e + f = 2, $$ so $$ f = 2 - v + e. $$ Substitute into \(3f \leq 2e\): $$ 3(2 - v + e) \leq 2e. $$ Thus $$ 6 - 3v + 3e \leq 2e, $$ and therefore $$ e \leq 3v - 6. $$ This inequality gives a simple test for nonplanarity. If a simple graph has more than \(3v - 6\) edges, then it cannot be planar. ## 36.6 Bipartite Planar Graphs If \(G\) is simple, bipartite, planar, and has at least three vertices, then $$ e \leq 2v - 4. $$ The reason is that a bipartite graph has no odd cycle. In particular, it has no triangle. Therefore every face boundary has length at least four. Counting edge appearances around faces gives $$ 4f \leq 2e. $$ Using Euler's formula again, $$ f = 2 - v + e. $$ Substitute: $$ 4(2 - v + e) \leq 2e. $$ Then $$ 8 - 4v + 4e \leq 2e, $$ so $$ e \leq 2v - 4. $$ This proves that \(K_{3,3}\) is nonplanar. The graph \(K_{3,3}\) has $$ v = 6, \qquad e = 9. $$ But a simple bipartite planar graph with six vertices must satisfy $$ e \leq 2 \cdot 6 - 4 = 8. $$ Since \(9 > 8\), \(K_{3,3}\) is not planar. ## 36.7 The Nonplanarity of \(K_5\) The complete graph \(K_5\) has $$ v = 5, \qquad e = 10. $$ If \(K_5\) were planar, it would satisfy $$ e \leq 3v - 6. $$ But $$ 3v - 6 = 3 \cdot 5 - 6 = 9. $$ Since \(10 > 9\), the graph \(K_5\) is not planar. This argument is short, but it is important. It shows how a counting theorem about all planar graphs can rule out planarity without examining every possible drawing. ## 36.8 Maximal Planar Graphs A planar graph is maximal planar if no new edge can be added without destroying planarity. In a simple maximal planar graph with at least three vertices, every face is bounded by a triangle. Such a graph is also called a triangulation of the plane. For a maximal planar graph, $$ e = 3v - 6 $$ and $$ f = 2v - 4. $$ These formulas follow from Euler's formula and the fact that every face has boundary length three. Maximal planar graphs are dense among planar graphs. They have as many edges as a simple planar graph on the same number of vertices can have. ## 36.9 Planarity Is Topological Planarity does not depend on the precise shape of the edges. Edges may be straight lines, arcs, or more general curves. What matters is whether the graph can be embedded in the plane without crossings. This makes planarity a topological property. The drawing may be stretched or bent, but it must preserve which vertices are joined by edges and must avoid unintended intersections. A planar graph can also be drawn on a sphere, and a graph drawn on a sphere can be projected onto the plane. Thus planar graph theory may be viewed either on the plane or on the sphere. ## 36.10 Planarity and Subgraphs If a graph is planar, then every subgraph is planar. Removing vertices or edges cannot create a crossing that was not already present. The contrapositive is often useful: If a graph contains a nonplanar subgraph, then the graph is nonplanar. Since \(K_5\) and \(K_{3,3}\) are nonplanar, any graph containing either as a subgraph is nonplanar. A deeper theorem, Kuratowski's theorem, says that these two graphs are the fundamental obstructions to planarity, after allowing subdivisions. This result will be studied later. ## 36.11 Summary A planar graph can be drawn in the plane without edge crossings. A plane graph is a planar graph with a fixed crossing-free embedding. Such an embedding divides the plane into faces, including the outer face. For every connected plane graph, $$ v - e + f = 2. $$ This formula implies strong restrictions on planar graphs. A simple planar graph satisfies \(e \leq 3v - 6\), and a simple bipartite planar graph satisfies \(e \leq 2v - 4\). These inequalities prove immediately that \(K_5\) and \(K_{3,3}\) are nonplanar. Planar graph theory studies the interaction between graph structure and surface embedding. It is the foundation for map coloring, graph drawing, network layouts, topological graph theory, and many algorithmic problems.