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. (For example, if two highways need to cross without intersecting, then an overpass needs to be built, which is expensive.) 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.

This drawing of a graph has several edges that cross:

However, the graph is planar, because there is a different picture in which no edges cross:

After we have some more theory, we will be able to give easier proofs of the next two results (see Corollary 15.2.5 and Corollary 15.2.6).

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{.}\)

⬛

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 divides 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 an important characterization 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.1. The white vertices are the new ones.

Figure 15.1.1. 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. Draw the dual graph of each of the two planar embeddings in Example 15.1.11.

  2. 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.

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

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

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

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

    Use Kuratowski's Theorem.

  7. 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.)

Remark 15.1.17.

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{.}\)