1. Introduction

In this tutorial, we’ll talk about planar graphs and present some of their fundamental properties.

2. Planar Graphs

A planar graph \boldsymbol{G = (V, E)} is the one we can draw on the plane so that its edges don’t cross (except at nodes). A graph drawn in that way is also also known as a planar embedding or a plane graph.

So, there’s a difference between planar and plane graphs. A plane graph has no edge crossings, but a planar graph may be drawn without them. For example:

Plane graph

G_1 is a planar but not a plane graph, whereas G_2 is a plane graph. G_1 is planar because it is isomorphic to G_2.

2.1. Isomorphism

Formally, a planar graph is isomorphic to a plane graph.

G_1(V_1, E_1) and G_2(V_2, E_2) are isomorphic graphs if there’s a 1-1 mapping F: V_1 \rightarrow V_2 of their vertices, and the following holds:

    [\forall (u, v) \in V_1, (u, v) \in E1 \iff (F(u), F(v)) \in E_2]

For example:

isomorphic graphs

All three graphs are isomorphic to one another. The top left and the bottom graphs have the identity isomorphism (F(u)=u), whereas the isomorphism of the top right graph is F(a)=d, F(c)=b, F(d)=c, F(b)=a.

3. Properties of Planar Graphs

Let’s check out some properties of planar graphs.

3.1. Faces

A graph defines connected regions on a plane we call faces, each of which is bordered by graph edges:

faces

Any face’s boundary contains the vertices and edges of the graph G that separate it from other regions.

One unbounded region, known as the exterior region, exists in every plane graph.

The number of edges constituting the boundary of a face f is its degree. In other terms, the length of the face’s boundary determines its degree.

For instance, the faces f_1, f_2, and f_3 of G in the above image have the degree of d(f_1)=d(f_2)=d(f_3)=3.

3.2. Chromatic Number

As we recall from graph theory, the chromatic number of a graph is the least amount of colors necessary to color the vertices of a graph G such that no two adjacent nodes have the same color. Any planar graph’s chromatic number is always less than or equal to 4.

As a result, any planar graph always requires a maximum of four colors to color its vertices. For instance:

Chromatic Number planar graph

This planar graph’s chromatic number is 4.

3.3. Proving a Graph Is (Not) Planar

There are several properties of planar graphs we can use in proofs:

  1. If a connected planar graph G has e edges and r regions or faces then r\leq \frac{2}{3} e
  2. If a connected planar graph G has e edges, v vertices, and r regions, then v - e + r = 2
  3. If a connected planar graph G has e edges and v vertices, then 3v -e \geq 6
  4. A complete graph K_n is a planar iff n < 5
  5. A complete bipartite graph K_{m,n} is planar iff m<3 or n \geq 3
  6. If and only if a subgraph of graph G is homomorphic to K_5 or K_{3, 3}, then G is considered to be non-planar

A graph homomorphism is a mapping between two graphs that considers their structural differences. More precisely, a graph G=(V, E) is homomorphic to G'=(V', E') if there’s a mapping f: V \rightarrow  V' such that (x, y) \in E  \implies (f(x, f(y)) \in E'. It maps vertices adjacent in G to vertices adjacent in G'.

The first three state the necessary conditions for planarity. For example, if we have a connected graph such that 3v - e < 6, we know it isn’t planar. However, necessary conditions aren’t sufficient, which means that some non-planar graphs can satisfy them. Therefore, we can use those properties to prove that a graph isn’t planar, not that it is.

The last property allows us to prove if a graph is planar. If we can’t find \boldsymbol{K_5} or \boldsymbol{K_{3,3}} in our graph, then we can be sure it’s planar.

3.4. Non-Planar Graphs

Non-planar graphs can’t be drawn in a plane without crossing edges.

Two well-known types of non-planar graphs are K_5, a complete graph with 5 vertices, and K_{3, 3}, a complete bipartite graph with 3 vertices in each bipartition:

Non-planar graphs

The importance of these two graphs lies in the fact that any non-planar graph contains them as subgraphs.

4. Conclusion

In this article, we discussed planar graphs, one of the most widely used graph theory concepts.

A planar graph is a graph that can be drawn on a plane such that its edges intersect only at their end nodes. A plane graph is a graph whose edges don’t intersect. So, we call a graph planar if we can draw it as a plane graph.

To prove that a graph is planar, we need to show that it doesn’t contain the complete graph \boldsymbol{K_5} or the complete bipartite graph \boldsymbol{K_{3,3}}.