## Planar Graphs Demystified

A planar graph is a graph that can be drawn on the plane with no intersecting arcs. The edges can intersect only at endpoints. Let’s look at a couple of planar graphs.

Let’s also take a quick look at a graph that is not planar. This is the famous K5 graph. We’ll attempt to make it planar.

After step 1, we can see that intersecting edges still exist. Let’s see what step 2 and 3 look like.

We can see that in step 2, it still looks promising. There’s only one additional intersecting edge that must be dealt with. However, once we attempt to move it in any direction, there will always be an intersect. You can see that the intersection occurs in step 3. K5 is therefore a non-planar graph.

K5 graph is a famous non-planar graph; K3,3 is another. Draw out the K3,3 graph and attempt to make it planar. You’ll quickly see that it’s not possible.

Do we have to attempt to make the planar graph by redrawing it every single time? No, since we have the Euler formula. Euler’s formula states that the number of vertices minus the number of edges plus the number of faces must equal 2 on a planar graph.

v – e + f = 2

Let’s test this with a couple of small examples.

The graph on the left has 4 vertices, 4 edges, and 2 faces. The outside of the graph is also considered a face. If we plug those values into Euler’s equation, we get 4 – 4 + 2 = 2. So, this is a planar graph. The example on the right has 4 vertices, 6 edges, and 4 faces. If we plug those values into Euler’s equation, we get 4 – 6 + 4 = 2. Since 2 equals 2, we can see that the graph on the right is a planar graph as well.

There’s another simple trick to keep in mind. Complete graphs (Kn), where each vertex is connected to all of the other vertices in the graph, are not planar if n ≥ 5. So, K5, K6, K7, …, Kn graphs are not planar. Complete bipartite graphs (Km,n) are not planar if m ≥ 3 and n ≥ 3. We can quickly verify that the K3,3 graph is not planar then.

Of course, it’s not always that simple. The general rule of thumb is that if you can find a K3,3 or a K5 subgraph, then the graph is not planar. Let’s see if we can prove that the following graph is not planar.

After observing the graph, we can quickly see that vertices 2, 3, 5, 7, 8, and 9 have 3 edges connecting to each of them. We can move towards the direction of proving that this will be a K3,3 graph. Let’s draw those points on a plane.

If we can rearrange the graph above so that each of those points encompasses all the other vertices and still maintains three edges each, then that sufficiently proves that this is a K3,3 graph and is not planar.

We’ll start by connecting vertices 2 and 7 since there is a direct connection.

Node 2 is also directly connected to node 3.

We need node 2 to be connected to one additional node. It looks like if we follow its path to the left, it connects to node 9 through nodes 12, 11, and 10. To make it clearer, to get to node 9, we’ll take a path from node 2 through edge 2–1, then through edge 1–12, then through edge 12–11, then through edge 11–10, and finally through edge 10–9.

Moving on to edge 3, it’s connected to node 8 directly.

When comparing the graph on the left with the graph on the right, we can see that in the left graph node 3 is connected to node 4. However, in our graph on the right, node 4 does not exist. But, node 5 exists. We can see that node 3 is connected to node 5 through node 4.

Moving on to node 5, it’s connected directly to node 9.

Node 5 is also connected indirectly to node 7 through node 6.

Node 7 is connected directly to node 8.

And finally, node 8 is connected directly to node 9.

Since each of the vertices in the graph we produced on the right is connected to 3 edges, this shows that the graph produced is a K3,3 graph, which we know for a fact is non-planar. Therefore, the graph on the left is non-planar as well.

If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.