Skip to main content

Section 15.1 Planar graphs

Visually, there is always a risk of confusion when a graph is drawn in such a way that some of its edges cross over each other. Also, in physical realisations of a network, such a configuration can lead to extra costs (think about building an overpass as compared to building an intersection). It is therefore helpful to be able to work out whether or not a particular graph can be drawn in such a way that no edges cross.

Definition 15.1.1.

A graph is planar if it can be drawn in the plane (\(\mathbb R^2\)) so edges that do not share an endvertex have no points in common, and edges that do share an endvertex have no other points in common.

Such a drawing is called a planar embedding of the graph.

The following graph is planar:

Here is a planar embedding:

Label the vertices of \(K_5\) as \(v_1, \ldots, v_5\text{.}\) Consider the \(3\)-cycle \((v_1, v_2, v_3, v_1)\text{.}\) The vertex \(v_4\) must lie either inside or outside the boundary determined by this \(3\)-cycle. Furthermore, since there is an edge between \(v_4\) and \(v_5\text{,}\) the vertex \(v_5\) must lie on the same side (inside or outside) as \(v_4\text{.}\)

Suppose first that \(v_4\) and \(v_5\) lie inside the boundary. The edges \(v_1v_4\text{,}\) \(v_2v_4\text{,}\) and \(v_3v_4\) divide the area inside the boundary into three regions, and \(v_5\) must lie inside one of these three regions. One of \(v_1\text{,}\) \(v_2\text{,}\) and \(v_3\) is not a corner of this region, and in fact lies outside of it while \(v_5\) lies inside of it, making it impossible to draw the edge from this vertex to \(v_5\text{.}\)

The proof is similar if \(v_4\) and \(v_5\) lie on the outside of the boundary determined by the \(3\)-cycle \((v_1, v_2, v_3, v_1)\text{.}\)

Label the vertices in one of the bipartition sets as \(v_1, v_2, v_3\text{,}\) and the vertices in the other part as \(u_1, u_2, u_3\text{.}\) Consider the \(4\)-cycle

\begin{equation*} (v_1,u_1,v_2,u_2,v_1)\text{.} \end{equation*}

The vertex \(v_3\) must lie either inside or outside the boundary determined by this \(4\)-cycle. Furthermore, since there is an edge between \(v_3\) and \(u_3\text{,}\) the vertex \(u_3\) must lie on the same side (inside or outside) as \(v_3\text{.}\)

Suppose first that \(v_3\) and \(u_3\) lie inside the boundary. The edges \(v_3u_1\) and \(v_3u_2\) divide the area inside the boundary into two regions, and \(u_3\) must lie inside one of these two regions. One of \(v_1\) and \(v_2\) does not lie on the boundary of this region, and in fact lies outside of it while \(u_3\) lies inside of it, making it impossible to draw the edge from this vertex to \(u_3\text{.}\)

The proof is similar if \(v_3\) and \(u_3\) lie on the outside of the boundary determined by the \(4\)-cycle \((v_1, u_1, v_2, u_2, v_1)\text{.}\)

However, both \(K_5\) and \(K_{3,3}\) can be embedded onto the surface of what we call a torus (a doughnut shape), with no edges meeting except at mutual endvertices. Embeddings are shown in Figures 15.1.1 and Figure 15.1.2.

The dotted edge wraps around through the hole in the torus.

Figure 15.1.1. \(K_5\) embedded on a torus

The dotted edge wraps around through the hole in the torus.

Figure 15.1.2. \(K_{3,3}\) embedded on a torus

You might think at this point that every graph can be embedded on the torus without edges meeting except at mutual endvertices, but this is not the case. In fact, for any surface there are graphs that cannot be embedded in that surface (without any edges meeting except at mutual endvertices).

For any embedding of a planar graph, there is another embedded planar graph that is closely related to it, which we will now describe. Notice that a planar embedding partitions the plane into regions.

Definition 15.1.5.

The regions into which a planar embedding partitions the plane, are called the faces of the planar embedding.

In these drawings, we have labeled the faces of the two planar embeddings with \(f_1\text{,}\) \(f_2\text{,}\) etc., to show them clearly.

Notation 15.1.7.

We use \(F(G)\) (or simply \(F\) if the graph is clear from the context) to denote the set of faces of a planar embedding.

Definition 15.1.8.

We say that an edge is incident with a face of a planar embedding, if it lies on the boundary of the face (or inside the face).

For a planar embedding of \(G\text{,}\) the dual graph or planar dual, \(G^*\), is defined by \(V(G^*)=F(G)\text{,}\) and \(f_i \sim f_j\) if and only if there is an edge of \(G\) that is incident with both \(f_i\) and \(f_j\text{.}\)

It is possible that the dual graph of a planar embedding will not be a simple graph, even if the original graph was simple.

Here we show how to find the planar duals of the embeddings given in Example 15.1.6. We include the original embedding as above; the grey vertices and dashed edges are the vertices and edges of the dual graph.

Note that the second graph has loops and multiedges. Note also that although \(f_1\) and \(f_5\) meet at a vertex in the embedding of the first graph, they are not adjacent in the dual since they do not share a common edge.

Some other useful observations:

  • \(|E(G)|=|E(G^*)|\text{,}\) and every dashed edge crosses exactly one black edge;

  • the valency of the vertex \(f_i\) in \(G^*\) is equal to the number of edges you trace, if you trace around the perimeter of the face \(f_i\) in \(G\) (so edges that dangle inside the face get counted twice).

Both of these facts follow fairly directly from the definitions.

Be careful! — Two different planar embeddings of the same graph may have nonisomorphic dual graphs, as we show here.

In the planar dual of the embedding on the left, \(f_1\) will have valency \(3\text{;}\) \(f_2\) and \(f_3\) will have valency \(4\text{;}\) and \(f_4\) will have valency \(7\text{.}\) In the planar dual of the embedding on the right, \(f_1\) will have valency \(3\text{;}\) \(f_2\) will have valency \(5\text{;}\) \(f_4\) will have valency \(4\text{,}\) and \(f_3\) will have valency \(6\text{.}\) Since the lists \(3,4,4,7\) and \(3,4,5,6\) are not permutations of each other, the planar duals cannot be isomorphic.

Before moving on to other related topics, we present a classification of planar graphs. This is a theorem by Kazimierz Kuratowski (1896—1980) (from whose name the notation for complete graphs is taken). He proved this result in \(1930\text{.}\)

We need one new definition.

Definition 15.1.12.

An edge \(uv\) can be subdivided by placing a vertex somewhere along its length. Technically, this means deleting \(uv\text{,}\) adding a new vertex \(x\text{,}\) and adding the edges \(ux\) and \(vx\text{.}\)

A subdivision of a graph is a graph that is obtained by subdividing some of the edges of the graph.

An example is shown in Figure 15.1.3. The white vertices are the new ones.

Figure 15.1.3. A subdivision of \(K_5\)

One direction of the proof is fairly straightforward, since we have already proven that \(K_5\) and \(K_{3,3}\) are not planar. However, we won't try to prove this theorem in this course.

A subdivision of \(K_5\) or of \(K_{3,3}\) will sometimes be very difficult to find, but efficient algorithms do exist.

Typically, to prove that a graph is planar you would find a planar embedding. To prove that a graph is not planar, you would find a subgraph that is a subdivision of either \(K_5\) or \(K_{3,3}\text{.}\)

Find a subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\) in this graph, to show that it is not planar.

Solution

Here is a subdivision of \(K_{3,3}\) in the given graph. The white vertices are the vertices that are subdividing edges. Unnecessary edges have been deleted. The bipartition consists of \(\{a,c,e\}\) and \(\{b,g,h\}\text{.}\)

  1. Prove that if a graph \(G\) has a subgraph \(H\) that is not planar, then \(G\) is not planar. Deduce that for every \(n \ge 6\text{,}\) \(K_n\) is not planar.

  2. Find a planar embedding of the following graph, and find the dual graph of your embedding:

  3. Find a planar embedding of the following graph, and find the dual graph of your embedding:

  4. The graph in Example 15.1.15 also has a subgraph that is a subdivision of \(K_5\text{.}\) Find such a subgraph.

  5. Prove that the Petersen graph is not planar.
    Hint

    Use Kuratowski's Theorem.

  6. Find planar embeddings of the two graphs pictured below. (These graphs are obtained by deleting an edge from \(K_5\) and deleting an edge from \(K_{3,3}\text{,}\) respectively.)

Rather than embedding graphs onto a different surface (such as a torus) to avoid edges that cross, it sometimes makes more sense to ask what is the fewest number of possible edge-crossings, for any embedding of the graph into the plane. Certainly for many real-life applications, this may be more useful, as we are looking at the smallest number of overpasses that may be required, or places where we need to add insulation into a chip so that wires that cross do not interfere with each other.

Even this number can get very large, and for some purposes it is more useful to consider how many times any given edge must participate in edge-crossings. Under this model, it is better to spread around the edge crossings so that no edge participates in more than one (for example), than to have one edge appear in all of the crossings, even if this lowers the total number of crossings.

With this in mind, we define a graph to be \(k\)-planar if it can be drawn in the plane so that no edge participates in more than \(k\) edge-crossings.

It is possible to test for planarity in linear time, using Kuratowski's Theorem or Wagner's Theorem (which we will discuss later in this chapter), and even to find a planar embedding if the graph is planar, or a minimal subgraph obstructing planarity if the graph is non-planar. One of the best of the known algorithms is the “edge addition method” due to John M. Boyer (1968—) and Wendy Joanne Myrvold (1961—) from \(2004\text{.}\) In contrast, testing whether or not a graph is \(1\)-planar is known to be NP-complete. In fact, in a \(2020\) preprint (accepted but not yet published at the time of this edit), John Cameron Urschel (1991—) and Jake Wellens (1992—) have shown that testing whether or not a graph is \(k\)-planar for any \(k\ge 1\) is NP-complete.