Planar Graphs and Plane Drawings
| Definition: A graph is considered Planar if it can be redrawn such that no edges intersect. That is, a graph is planar if there exists a plane drawing of the graph. |
In many instances, we may want to see if a graph can be redrawn without any edge intersection using what is called a Plane Drawing. Note that edges meeting at a vertex does not count as an edge intersection. For example, the following graph is considered planar:
Because there exists a plane drawing of the graph, that is, a reconfiguration of the location of the edges so that no edges in the graph intersect. Some graphs are not planar though since there is no possible plane drawing of the graph, for example, the complete bipartite graph $K_{3,3}$:
is not considered planar since there must be at least one edge intersection in the graph. Nevertheless, there are some types of graphs that always have a plane drawing:
| Graph Type | Always Planar? (Y/N) |
|---|---|
| Cycle Graphs, $C_n$ | Yes. This should be rather obvious, but every cycle can be drawn as a ring of edges and vertices, and clearly there is no edge intersections in a ring. |
| Path Graphs, $P_n$ | Yes. Like cycle graphs, this should be rather obvious. A path graph can always be drawn as a straight line of edges and vertices and is hence always planar. |
| Tree Graphs | Yes. Tree graphs are always planar since they contain no cycles. Just because a graph has cycles does not mean that it isn't planar, however, issues of planarity arise with regards to cycles. |
Nevertheless, determining whether a graph can be designed to be planar or not is important in many fields. For example, in circuitry, it is often necessary to make sure that no two electrical connections intersect. Another example of the importance of planar configurations is in determining routes and travel locations. If we want to design an air route, we certainly do not want the paths of two planes to intersect!
The Degree of a Face
| Definition: For a planar graph G containing a face $f_n$, the Face Degree denoted $\deg (f_n)$ is the number of edges forming the face $f_n$. |
As an example, let's look at the following graph:
The following table states the face degree of each face:
| Face # | Degree of the Face |
|---|---|
| $1 �938��939� [[$ \deg(f_1) = 3$ | |
| $2 �944��945� [[$ \deg(f_2) = 4$ | |
| $3 �950��951� [[$ \deg(f_3) = 3$ | |
| $4 �956��957� [[$ \deg(f_4) = 6$ |
The Handshaking Lemma for Planar Graphs
| Lemma 1: In any connected planar graph $G$, the sum of the face degrees is equal to twice the number of edges, that is, for a planar graph with $k$ faces $\sum_{i = 1}^{k} \deg (f_i) = 2 \mid E(G) \mid$. |
We can verify the handshaking lemma for planar graphs with the example from earlier. We note that the graph above was both planar and connected. The sum of the face degrees is $16$, which is twice the number of edges in the graph ($8$).
We will omit a formal proof for planar graphs, however, we note that on each side of the edge, there is a face. Hence, each edge in a planar graph contributes to $+2$ of the sum of the face degrees.
We are now ready to prove a planar graph version of Euler's Formula.
| Theorem 1: If $G$ is a connected planar graph, then $v + f - e = 2$. |
Like said before, the theorem is a direct consequence of Euler's Formula that we saw earlier where $v$ represents the number of vertices in the graph, $f$ represents the number of faces, and $e$ represents the number of edges.
- Proof: We will now use Euler's formula to prove Theorem 1 first by induction.
- Suppose that we have a spanning tree on $v$ vertices. The addition of any edge to this spanning tree will also create a new face. Hence, whenever the number of edges is incremented, so is the number of faces. Let $S(v, e, f)$ be the statement that for a connected planar graph, $v + f - e = 2$.
- Base Step: For a spanning graph, there will be exactly $v$-vertices, $e$-edges, and $1$ face (the infinite face). Hence it follows that $v + 1 - e = 2$, or more appropriately that $v = e + 1$, which is true since this property is one of the defining aspects of a tree.
- Induction Step: Suppose that Euler's formula holds and that we look at adding an edge. Hence there will be $e+1$ edges. But since we started with a maximum spanning graph, the addition of an edge will result in another face, so there will be $f+1$ faces. Note that the number of vertices will not change, hence we are looking at the statement $S(v, e+1, f+1)$. Hence if we suppose Euler's formula is true, then it follows that $v + (f + 1) - (e + 1) = 2$, or rather $v + f - e = 2$, which is still true.
- Conclusion: By the principle of mathematical induction, $S(v, e, f)$ is true. $\blacksquare$