Planar Graphs

When is it possible to draw a graph so that none of the edges cross? If this is possible, we say the graph is planar (since you can draw it on the plane).

Notice that the definition of planar includes the phrase it is possible to. This means that even if a graph does not look like it is planar, it still might be. Perhaps you can redraw it in a way in which no edges cross. For example, this is a planar graph:

That is because we can redraw it like this:

The graphs are the same, so if one is planar, the other must be, too. However, the original drawing of the graph was not a planar representation of the graph.

When a planar graph is drawn without edges crossing, the edges and vertices of the graph divide the plane into regions. We will call each region a face. The graph above has 3 faces (yes, we do include the outside region as a face). The number of faces does not change no matter how you draw the graph (as long as you do so without the edges crossing), so it makes sense to ascribe the number of faces as a property of the planar graph.

WARNING: you can only count faces when the graph is drawn in a planar way. For example, consider these two representations of the same graph:

If you try to count faces using the graph on the left, you might say there are 5 faces (including the outside). But drawing the graph with a planar representation shows that in fact there are only 4 faces.

There is a connection between the number of vertices (\(v\)), the number of edges (\(e\)), and the number of faces (\(f\)) in any connected planar graph. This relationship is called Euler's formula.

For any connected planar graph with \(v\) vertices, \(e\) edges, and \(f\) faces, we have \[v-e + f = 2\].

Why is Euler's formula true? One way to convince ourselves of its validity is to draw a planar graph step by step. Start with the graph \(P_2\):

Any connected graph (besides just a single isolated vertex) must contain this subgraph. Now we build up to our graph by adding edges and vertices. Each step will consist of either adding a new vertex connected by a new edge to part of your graph (so creating a new spike) or by connecting two vertices already in the graph with a new edge (completing a circuit).

What do these moves do? When adding the spike, the number of edges increases by 1, the number of vertices increases by 1, and the number of faces remains the same. But this means that \(v - e + f\) does not change. Completing a circuit adds one edge, adds one face, and keeps the number of vertices the same. So again, \(v - e + f\) does not change.

Since we can build any graph using a combination of these two moves, and doing so never changes the quantity \(v - e + f\), that quantity will be the same for all graphs. But notice that our starting graph \(P_2\) has \(v = 2\), \(e = 1\), and \(f = 1\), so \(v - e + f = 2\).

The argument we have outlined above is not quite correct, since we made the unjustified assumption that all graphs can be built up from \(P_2\) using only the two moves we described. To avoid this issue, we can use a minimal criminal argument. You are asked to do this in the exercises, but the idea is essentially the same as we have here, except that we start with a minimal connected planar graph that does not satisfy the formula, then remove either an edge or a vertex (and its edge) to get a smaller connected planar graph that does satisfy the formula. But just like the adding moves we have described above, removing an edge or a vertex does not change the quantity \(v - e + f\).

Not all graphs are planar. If there are too many edges and too few vertices, then some of the edges will need to intersect. The smallest graph where this happens is \(K_5\).

If you try to redraw this without edges crossing, you quickly get into trouble. There seems to be one edge too many. In fact, we can prove that no matter how you draw it, \(K_5\) will always have edges crossing.

The other simplest graph which is not planar is \(K_{3,3}\)

Proving that \(K_{3,3}\) is not planar answers the classic houses and utilities puzzle: it is not possible to connect each of three houses to each of three utilities without the lines crossing.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Another area of mathematics where you might have heard the terms vertex, edge, and face is geometry. A polyhedron is a geometric solid made up of flat polygonal faces joined at edges and vertices. We are especially interested in convex polyhedra, which means that any line segment connecting two points on the interior of the polyhedron must be entirely contained inside the polyhedron. An alternative definition for convex is that the internal angle formed by any two faces must be less than \(180\deg\).

Notice that since \(8 - 12 + 6 = 2\), the vertices, edges, and faces of a cube satisfy Euler's formula for planar graphs. This is not a coincidence. We can represent a cube as a planar graph by projecting the vertices and edges onto the plane. One such projection looks like this:

In fact, every convex polyhedron can be projected onto the plane without edges crossing. Think of placing the polyhedron inside a sphere, with a light at the center of the sphere. The edges and vertices of the polyhedron cast a shadow onto the interior of the sphere. You can then cut a hole in the sphere in the middle of one of the projected faces and stretch the sphere to lie down flat on the plane. The face that was punctured becomes the outside face of the planar graph.

The point is, we can apply what we know about graphs (in particular planar graphs) to convex polyhedra. Since every convex polyhedron can be represented as a planar graph, we see that Euler's formula for planar graphs holds for all convex polyhedra as well. We also can apply the same sort of reasoning we use for graphs in other contexts to convex polyhedra. For example, we know that there is no convex polyhedron with 11 vertices all of degree 3, as this would make 33/2 edges.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Let's return to the problem of providing lines for water, electricity, and natural gas to three homes which we discussed in the introduction to this chapter. How can we model this problem using a graph? The best way is to have a vertex for each utility and a vertex for each of the three homes. Then what we're asking is if we can draw the graph that has an edge from each utility to each home so that none of the edges cross. This graph is shown in . You should recognize it as the complete bipartite graph \(\bfK_{3,3}\) we introduced earlier in the chapter.

While this example of utility lines might seem a bit contrived, since there's really no good reason that the providers can't bury their lines at different depths, the question of whether a graph can be drawn in the plane such that edges intersect only at vertices is a long-studied question in mathematics that does have useful applications. One area where it arises is in the design of microchips and circuit boards. In those contexts, the material is so thin that the option of placing connections at different depths either does not exist or is severely restricted. There is much deep mathematics that underlies this area, and this section is intended to introduce a few of the key concepts.

By a drawing of a graph, we mean a way of associating its vertices with points in the Cartesian plane \(\reals^2\) and its edges with simple polygonal arcs whose endpoints are the points associated to the vertices that are the endpoints of the edge. You can think of a polygonal arc as just a finite sequence of line segments such that the endpoint of one line segment is the starting point of the next line segment, and a simple polygonal arc is one that does not cross itself. (Our choice of polygonal arcs rather than arbitrary curves actually doesn't cause an impediment, since by taking very, very, very short line segments we can approximate any curve.) A planar drawing of a graph is one in which the polygonal arcs corresponding to two edges intersect only at a point corresponding to a vertex to which they are both incident. A graph is planar if it has a planar drawing. A face of a planar drawing of a graph is a region bounded by edges and vertices and not containing any other vertices or edges.

shows a planar drawing of a graph with \(6\) vertices and \(9\) edges. Notice how one of the edges is drawn as a true polygonal arc rather than a straight line segment. This drawing determines \(5\) regions, since we also count the unbounded region that surrounds the drawing.

shows a planar drawing of the complete graph \(\bfK_4\). There are \(4\) vertices, \(6\) edges, and \(4\) faces in the drawing.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.