Kuratowski’s theorem might seem counterintuitive, defining a planar graph in terms of what it can’t contain. It was, however, an important tool to
- Recognize that two categories of graphs (complete and complete bipartite) are non-planar (except for their smallest specimens), and there’s no need to try to find ways to avoid intersections when drawing them.
- Mathematically prove when a graph isn’t planar.
Although it was a great tool for mathematical proofs, using it for an algorithm that automatically checks if a graph is planar was another story.
We’ll see how to implement a planarity testing algorithm later in this section. First, let’s finish our discussion of Kuratowski’s graphs.
If we look at figure 15.5, that embedding of k5 has 5 points where edges cross; for each abstract graph G, however, there are infinitely many possible embeddings. As you can imagine, there are infinitely many ways you can draw G, moving each vertex a little bit (or a large bit) in any direction, and even using a different curve for the edges (for instance, infinitely many curves instead of segments).
This holds true for K5 as well, obviously. Now the point is, are all these embeddings equivalent, with respect to the way edges cross each other?
Well, we already know a way to draw K5 so that 5 pairs of edges cross, so if we can find another way where its edges cross more, or less, we have evidence that not all embeddings are the same.
Long story short, figure 15.7 shows an embedding for K5 with just a single cross-point between two edges.
Therefore, we can say that the answer to this question is no, they aren’t all equivalent. As a matter of fact, working to find the “best”[1] possible embedding for graphs will be our quest for the rest of this book.[2]
1. Using Kuratowski’s theorem in practice
Kuratowski’s theorem states that K5 and K3,3 are the “simplest” graphs that don’t have a planar embedding. What did he mean by “simplest”? Well, in this case it means that that there isn’t any smaller graph (meaning with fewer vertices or edges) that isn’t planar, and so every sub-graph of either K5 or K3,3 has a planar embedding.
I’ve always found it curious that there are two base cases. It wasn’t possible to find a single base graph because these two are fundamentally anisomorphic, but at the same time, it’s quite remarkable that any other non-planar graph can be reconducted just to these two.
You might wonder how we know both that there is no way to draw these graphs without intersections, and that there isn’t any simpler graph that’s not planar. Well, Kuratowski proved it, so we can trust his theorem.
But in case you still have doubts, you can also try to scramble the vertices in figure 15.7 and see if you can find a planar embedding; make yourself comfortable, because it might take a while, until you realize it’s not possible!
The other half of the claim, that there isn’t any smaller non-planar graph, is easier to show. Let’s focus on K5 and first look at a graph with fewer vertices, in particular K4, shown in figure 15.8.
At first sight, if we draw this graph naively, it seems like it has a pair of crossing edges. It’s easy, however, to move one of the vertices past the crossing point to obtain a planar embedding.
The other possibility to rule out is that there is a non-planar graph with fewer edges than k5; however, if we look at figure 15.7, it’s immediately obvious that if we remove either edge 1->5 or edge 2->3, then we also get rid of the one intersection in the drawing, as shown in figure 15.9. Since a complete graph is symmetrical and relabeling-invariant, we can obtain an equivalent embedding (ignoring the labels) regardless of which edge we remove from k5.
In conclusion, the largest sub-graphs of K5 are planar, and hence any other graph with 5 or less vertices and less than 9 edges is planar.
The same thing can be shown for K3,3; investigating its sub-graphs can be a good exercise to gain a better understanding of bipartite graphs and embeddings.
2. Planarity testing
Checking to see if a graph is planar is trickier than you might think. Even checking whether an embedding is planar isn’t that easy: that’s one of the tasks our brain performs easily, but it’s not that simple to replicate with an algorithm. If we want to avoid resorting to computer vision (and we usually do, for this kind of task) we need to restrict the way we draw edges, for instance, limiting to straight-line segments or Bezier curves, so that we can use math formulas to compute if they intersect. Still, the computational effort needed to check the number of intersections on a large graph remains considerable.
And this is just for a single embedding. Determining if a graph is non-planar means proving that for any possible embedding we can come up with, there is at least an intersection.
We already introduced Kuratowski’s work on planar graphs, providing the first method to determine if a graph is planar.
Planarity, however, had already been studied for a long time, and in fact Euler, in the 18th century, came up with an invariant (proved only in 1811 by Cauchy) providing necessary conditions for a graph to be planar.
Although these conditions are not sufficient, so they can’t be used to prove planarity, they are cheap to compute and, when violated, they rule out planarity.
The two conditions we can more easily implement in our tests are
- Given a simple, connected graph G=(V,E) with at least 3 vertices, G is planar only if |E| < 3|V| – 6.
- If |V| > 3 and G doesn’t have any cycle with length 3, then G is planar only if |E| < 2|V| – 4.
So, as a first step in a planarity test algorithm, we can check, in linear time O(V+E), both conditions: if either doesn’t hold, we already know that the answer is “non-planar”.
There are several algorithms to test for planarity. While none of them is particularly easy to implement, many are also inefficient: the first efficient algorithm, running in worst-case linear time, was derived only in 1974 by Hopcroft and Tarjan.
The inefficient algorithms that had been developed before would take up to O(|V|3), or even worse, as we’ll see.
One way to try to improve the situation is by using the divide-and-conquer strategy to break down the original graphs into smaller subgraphs that can be tested separately.
This is possible thanks to the following two lemmas:
- A graph is planar if and only if all its connected components are planar.
- A graph is planar if and only if all its biconnected components are planar.
In chapter 14 we have already given the definition of connected graph: G is connected when from any vertex v e G it is possible to find a path to any other vertex u e G. If a graph is not connected, we can define its connected components as the maximal disjoint subgraphs of G that are connected.
A biconnected graph is a connected graph with the additional property that there is not a single vertex v ϵ G such that removing v from G will disconnect the graph. An equivalent definition of a biconnected graph can be given: G is biconnected if for any pair of vertices u, v ϵ G there exist two disjoint paths between them. These two paths, therefore, can’t have any edge in common or any vertex except for u and v.
The proof of the first lemma is trivial. For a disconnected graph, because there are no edges between its connected components, it’s sufficient to draw each component such that it won’t overlap with the others.
As a consequence of the two lemmas, we can split any graph G into its biconnected components and apply the planarity testing of choice to each of them separately.
3. A naive algorithm for planarity testing
Since we have mentioned more than once that there is an (inefficient) algorithm based on Kuratowski’s theorem that is fairly straightforward to implement, let’s actually start from there. Listing 15.1 shows a template method that wraps any planarity testing algorithm, making sure we break down a graph into its connected (or, even better, biconnected) components and running the testing on each of them.
In chapter 14 we have seen how we can find the connected components of a graph using DFS; finding biconnected components is slightly more complicated, but it can still be done using a modified version of DFS.11
Now we need to define the actual method performing planarity testing on each biconnected (or connected) component. Listing 15.2 shows the method based on Kura- towski’s theorem.
The algorithm leverages the inductive definition of a graph. While trees can be defined by induction on the number of vertices (we construct larger trees by adding children to a root), given a graph G=(V,E), it can be inductively grown in two different ways.
As we have seen in chapter 14, in fact, it could be
- G’=(V+{v}, E): we add a new vertex to
- G’=(V, E+{(u,v)}) | u, v ϵ V: we add a new edge to G.
When it comes to decomposing G, therefore, we need to consider two sets of subgraphs:
- Induced subgraphs—All the graphs that could be obtained by individually removing each vertex of g (induction rule 1), and all the edges in turn touching the vertex removed.
- Spanning subgraphs—All the graphs that could be obtained by individually removing each edge of g (induction rule 2).
These two sets of graphs are recursively checked at lines #5-7 and #8-10, respectively. Since the algorithm is recursive, we need a base case: we could use the empty graph, trivially, but since we know that all graphs with 4 or fewer vertices are planar, we can stop our recursion earlier (see line #2) and save computational resources.
The only thing remaining is checking if the current input is a non-planar graph. Normally we would just use another base case (actually, 2), at line #4, where we check to see if recursion brought us either K5 or K3,3 (for Kuratowski’s theorem, we know that this means non-planar). In this case, though, we added another check at line #3, using Euler’s inequalities to our advantage: as we saw in section 15.2.2, if the graph we are examining has too many edges for its vertices, it must be non-planar.
To see how the utility methods performing these checks work, let’s take a look at listings 15.3, 15.4, and 15.5.
The method to check Euler’s constraints, shown in listing 15.3, is directly derived from the formulas in section 15.2.2. The hardest part is verifying that a graph doesn’t have any cycle of length 3: this can be done using a modified version of DFS that returns all cycles, and runs in linear O(V+E) time. Since this is quite expensive and requires a non-trivial effort to write and maintain the code, the benefit of including this second check is debatable and—especially on your first try—it might not be worth it: you can start with checking the first constraint only, and remove the if at line #5.
Listing 15.4 shows the method to check if a graph is (isomorphic to) K5. Obviously it needs to have 5 vertices (!), but we also know how many edges it should have, exactly 10. Notice that here we are talking about simple edges, where source and destination are distinct (so, no loops).
Listing 15.5 shows the method to check if a graph is (isomorphic to) K3,3. This is a bit more complicated because it’s not enough to check that the count of vertices (6) and edges (9) is right. We also need to check that the graph is bipartite and that both partitions have size 3.
This brings us to the last step we need to implement: finding out if a graph is bipartite, and retrieving the two partitions.
To do so, we exploit a property of bipartite graphs: a graph is bipartite if and only if it’s possible to color its vertices with exactly two different colors, such that there isn’t any pair of adjacent vertices with the same color. Figure 15.10 shows a few examples to clarify this definition.
We can perform graph coloring easily by modifying the BFS algorithm:
- We represent the source vertex as a red hexagon.
- Once we extract a vertex from the queue, we color all its neighbors with the opposite color: for example, blue squares (as shown in figure 15.10) if the current vertex is a red hexagon, and vice versa.
- If any of the adjacent vertices is already colored with the same color as the current vertex, then the graph is not bipartite.
Listing 15.6 shows the pseudo-code for a method returning the two partitions while it checks if the graph is bipartite. You can also take a look at a Java implementation on the book’s repo on GitHub or a JavaScript implementation provided by JsGraph, the JavaScript library that has been used to draw most of the examples of embeddings in this chapter.
4. Improving performance
This is the bulk of the simplest algorithm we have to test graph planarity. We know it’s inefficient, but exactly how inefficient?
It’s a recursive algorithm, where from each call to the method can stem several recursive calls; the depth of the recursion is already linear in the size of the original graph G= (V,E), because we remove one vertex or one edge at a time.
The breadth of the recursion tree (the number of recursive calls) is also linear, although in the size of the graph that is currently run on, let’s call it G’ = (V’, E’).
This is because the two for loops cycle through all vertices and all edges in G’.
We can write a formula for the running time. If |V’|=n, |E’|=m, then
T(n,m) = n * T(n-1, m) + m * T(n, m-1)
T(0,0) = 1
T(0,*)=1
T(*,0)=1
For a recurrence relation of the form T(n) = n * T(n-1), the solution depends on the value of the base term. If as in this case, T(0) = 1, then T (n) = n! – this, at least, when we have a single variable. Our specific case, where we have two variables, grows even faster.
The last thing we want in a formula for an algorithm’s running time is a factorial— a function that grows faster than the exponential function. This means that the algorithm, as presented in listing 15.2, can only be used for small graphs.
When you see a factorial pop up in your calculations, it will likely mean that you are computing the same thing over and over again, multiple times.
This is the case for our algorithm as well; let’s see an example, with a small graph with just three vertices. Let G=({1,2,3}, E) be our initial graph. For the sake of our example, we won’t bother with its edges, but focus on the recursion on vertices.
The for loop at line #4 of listing 15.2 will issue three calls for the following graphs:
(V’,E’)=({2,3}, E-{1}), ({1,3}, E-{2}), ({1,2}, E-{3})
Each of those graphs will in turn produce two calls:
({3}, E-{1,2}), ({2}, E-{1,3}),
({3}, E-{1,2}), ({1}, E-{2,3}),
({2}, E-{1,3}), ({1}, E-{2,3})
As you can see, in the second round of calls, each graph appears twice. If we also consider the recursion on the edges, it gets much worse.
Usually this kind of expansion ends up in a memory crash long before the recursion gets closer to the base cases.
The most common strategy for coping with this is to avoid the duplicates by one of the following:
- Define a better recursion that avoids the duplicates (not always possible).
- Prune the search tree avoiding duplicated work (branch and bound algorithms).
- Compute and store the results for the smaller cases and read them when needed while computing larger problems (dynamic programming algorithms).
For this problem, we can reasonably go for the third option and use memoization to provide a sort of cache of the results of the algorithm for smaller problems.
This will give us some improvement, but as we’ll see, the most efficient algorithms developed for planarity testing, instead, order the edges to be added or removed at each step in such a way to guarantee a linear number of steps (therefore using the first of the strategies in the list).
By avoiding computing things twice, we guarantee that we will examine each distinct subgraph at most once, so that the number of steps becomes bounded by the number of possible subgraphs. For a graph with n vertices and m edges, there are 2n induced subgraphs (because there are 2n subset of vertices) and 2m spanning subgraphs (considering the subset of edges). The total number of possible subgraphs is thus bounded by 2n+m, which is better than factorial, but still too large to consider the algorithm usable for graphs with more than ~20 vertices.
There are other small improvements that we can add; although not as impactful as avoiding duplicates, they all contribute to speeding up the algorithm. For instance, we can improve our halting condition. We don’t need to wait until we get down to K5 or K33; any complete graph with 5 or more vertices, or any complete bipartite graph with both partitions having 3 or more vertices, is certainly non-planar.
Most of these cases, however, are already caught by Euler’s invariants.
Listing 15.7 shows the pseudo-code for the improved method; you can find a Java implementation on the book’s repo or a JavaScript implementation provided by JsGraph.
5. Efficient algorithms
The algorithm presented in listing 15.7 is still too slow to be affordable on large graphs. Still, it can be a feasible, low-cost18 option that can work on small graphs.
There are far better algorithms that have been developed for planarity testing. While they take different approaches to provide an answer (and a planar embedding) in linear time, they all have something in common: they are fairly complicated.
As in, “research papers spanning dozens of pages” complicated. Describing them in detail goes beyond the scope of this chapter, but we’ll briefly describe a few prominent ones and provide pointers for the interested readers.19
Be aware that the effort to implement these algorithms might be consistent. Also keep in mind that if your constraints can be relaxed, and you can accept an algorithm that provides a reasonable embedding, even without guarantees that it will be planar, you can use simpler heuristics to generate embeddings (more on this later).
As we mentioned, the first linear-time algorithm for planarity testing was developed in 1974 by Hopcroft and Tarjan,20 improving a previously-developed21 O(|V|2) variant. Their idea is based on vertex addition, so the algorithm starts bottom-up, keeping the possible planar embeddings for each incrementally-built induced subgraph of the original one.
As we previously mentioned, this strategy defines a different approach to recursion: bottom-up rather than top-down, incremental and not divide-and-conquer, but above all, by carefully reconstructing the original graph one vertex at the time, it avoids analyzing all sub-graphs, and only performs a linear number of steps.
The key is that while adding vertices, the algorithm keeps track of the possible embeddings of the sub-graph.
Fast-forward to 2004, when a brand-new approach was developed by Boyer and Myrvold: it’s an edge-addition method, so it incrementally adds edges instead of vertices. It’s still linear, O(|V| + |E|), but it has the great advantage of avoiding any requirement for specific data structures to store the candidate embeddings. This algorithm is currently one of the state-of-the-art solutions to find planar embeddings for planar graphs; the best part is that you can find an open source implementation online on boost.org: http://mng.bz/5jj7.
The last algorithm we are going to mention is the planarity testing algorithm by Fraysseix, de Mendes, and Rosenstiehl, which is the other state-of-the-art algorithm in this area. It characterizes planar graphs in terms of a left-right ordering of the edges in a depth-first search tree, and its implementation is DFS-based, although obviously the DFS method needs to be modified accordingly, and it uses Tremaux trees, special spanning trees produced by a DFS visit of a graph.
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)