15.1: Planar Graphs
- Page ID
- 60149
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)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 with 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: Planar
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.
Example \(\PageIndex{1}\)
The following graph is planar:
Here is a planar embedding:
Theorem \(\PageIndex{1}\)
The graph \(K_5\) is not planar.
- Proof
-
Label the vertices of \(K_5\) as \(v_1, . . . , v_5\). Consider the \(3\)-cycle \((v_1, v_2, v_3, v_1)\). 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\), the vertex \(v_5\) must lie on the same side (inside or outside) as \(v_4\).
Suppose first that \(v_4\) and \(v_5\) lie inside the boundary. The edges \(v_1v_4\), \(v_2v_4\), 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\), \(v_2\), 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\).
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)\).
Theorem \(\PageIndex{2}\)
The complete bipartite graph \(K_{3,3}\) is not planar.
- Proof
-
Label the vertices in one of the bipartition sets as \(v_1\), \(v_2\), \(v_3\), and the vertices in the other part as \(u_1\), \(u_2\), \(u_3\). Consider the \(4\)-cycle
\[(v_1, u_1, v_2, u_2, v_1).\]
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\), the vertex \(u_3\) must lie on the same side (inside or outside) as \(v_3\).
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\).
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)\).
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 15.1.2.
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: Faces
The regions into which a planar embedding partitions the plane, are called the faces of the planar embedding.
Example \(\PageIndex{2}\)
In these drawings, we have labeled the faces of the two planar embeddings with \(f_1\), \(f_2\), etc., to show them clearly.
Notation
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: Dual Graph
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\), the dual graph or planar dual, \(G^∗\), is defined by \(V (G^∗) = F(G)\), and \(f_i ∼ f_j\) if and only if there is an edge of \(G\) that is incident with both \(f_i\) and \(f_j\).
It is possible that the dual graph of a planar embedding will not be a simple graph, even if the original graph was simple.
Example \(\PageIndex{3}\)
Here we show how to find the planar duals of the embeddings given in Example 15.1.2. 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^∗)|\), 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).
Proposition \(\PageIndex{1}\)
The dual graph of a planar embedding has a natural planar embedding, so is a planar graph. Furthermore, \((G^∗)^∗ = G\).
- Proof
-
Both of these facts follow fairly directly from the definitions.
Example \(\PageIndex{4}\)
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\); \(f_2\) and \(f_3\) will have valency \(4\); and \(f4\) will have valency \(7\). In the planar dual of the embedding on the right, \(f_1\) will have valency \(3\); \(f_2\) will have valency \(5\); \(f_4\) will have valency \(4\), and \(f_3\) will have valency \(6\). 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 Kuratowski (from whose name the notation for complete graphs is taken). He proved this result in \(1930\).
We need one new definition.
Definition: Subdivision
An edge \(uv\) can be subdivided by placing a vertex somewhere along its length. Technically, this means deleting \(uv\), adding a new vertex \(x\), and adding the edges \(ux\) and \(vx\).
A subdivision of a graph is a graph that is obtained by subdividing some of the edges of the graph.
Example \(\PageIndex{5}\)
An example is shown in Figure 15.1.3. The white vertices are the new ones.
Theorem \(\PageIndex{3}\): Kuratowski's Theorem
A graph \(G\) is planar if and only if no subgraph of \(G\) is a subdivision of \(K_5\) or \(K_{3,3}\).
- Proof
-
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}\).
Example \(\PageIndex{6}\)
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\}\).
Exercise \(\PageIndex{1}\)
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 ≥ 6\), \(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.6 also has a subgraph that is a subdivision of \(K_5\). 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}\), respectively.)