The Computer Scientist's Guide to Graph Theory, ep. 04
Where graph theory and geometry meet, beauty and challenge arise
Hi there! This post is a collaboration with Alejandro, taken directly from our upcoming book, The Hitchhiker's Guide to Graphs. This project grew out of our series in graph theory here, aiming to focus on the algorithmic aspects as well. We'll even implement our custom graph library from scratch.
The book is already available in early access, with instant updates to the content as we write it.
Alejandro is one of my favorite writers and one of my original inspirations for starting to talk about mathematics online. We complement each other in knowledge and style: He is a master of computer science and algorithms, and I make the necessary theoretical background as clear as possible.
If you would like to see what the book is like, check out our introductory series on graph theory:
Episode 00: What do your brain, your friends, and the city you live in have in common
Episode 01: Running into the woods: trees, forests, and spanning subgraphs
In the pulsating heart of Graphtopia, Major Groff von Veertex finds himself at the precipice of a technological breakthrough, with his vision of a groundbreaking supercomputer hanging in the balance. The superconductive material that promises unparalleled speeds and capabilities presents a formidable challenge: the circuits must be laid out without any overlaps.
To navigate this intricate labyrinth, Major Veertex calls upon the expertise of Dr. Adelaide Aligner, a renowned mathematician with a deep understanding of graph theory and its applications.
Dr. Aligner, a master of aligning and positioning complex structures, brings a sense of calm and determination to the Major's predicament. With her keen insight into graph layout, she proposes a solution that hinges on planarity testing, a mathematical technique that could ensure the supercomputer's circuits are laid out without a single overlap.
As the city of Graphtopia watches with bated breath, the stage is set for a dramatic partnership between Major Groff von Veertex and Dr. Adelaide Aligner, where mathematical prowess and innovative thinking converge to shape the future of this technological powerhouse.
Modeling the circuit design
The first step is, as usual, understanding the problem we need to solve in terms of nodes and edges. This case is different from previous chapters because we have always assumed that graph layouts are equivalent. We simply use the most convenient way of drawing it for illustrative purposes. But in this problem, the layout is the heart of the question.
So, to restate the problem in graph terms: Given a graph representing a circuit, where nodes are components and edges represent connections, is there a way to lay out the components in a plane so that no edges intersect?
In the language of graph theory, the question is to determine if our graph is planar; that is, it can be drawn on a plane without any intersecting edges.
We will precisely formalize this notion, but first, let’s break apart the problem to see if our intuitions fit the definition. When we translate real-life problems to math, we must often make assumptions. Here, the two key ones are:
the connection between any two nodes is a straight line, and
the relative sizes of the components don’t matter.
Take a minute to understand why our translation of the circuit design problem into graph theory relies on those key assumptions.
Done? In the remaining, we will challenge those assumptions and see if they significantly simplify our original problem or still capture its essence. Then, we will find necessary and sufficient conditions for determining whether any particular graph is planar. Finally, we will come up with a simple but clever algorithm to draw any planar graph.
Formalizing planarity
To understand what a planar graph is, we have to formalize a few notions first. Let’s talk about graph embeddings, that is, laying out a graph in the plane.
Definition 1. (Graph embeddings.) Let G = (V, E) be an arbitrary graph. An embedding 𝓔 of G is a mapping of G to ℝ², where
vertices in V correspond to points in ℝ²,
edges in E correspond to curves in ℝ²,
and the curve corresponding to the edge uv ∈ E connects the points representing u and v.
This definition formalizes the idea of drawing our graph onto a sheet of paper with points and connecting lines. This definition has nothing novel or fancy; it's just a mathematically formal way of expressing a simple concept.
(To be mathematically precise, we are talking about two-dimensional embeddings here. We can have n-dimensional embeddings, where objects are mapped onto ℝⁿ for an arbitrary n — which maybe you're familiar with from machine learning.)
Now let's define what a planar graph is.
Definition 2. (Planar graphs and embeddings.) Let G be an arbitrary graph.
(1) We say that an embedding of G is planar (or non-crossing) if no edges intersect.
(2) We say that G is a planar graph if it has a planar embedding.
(In some literature, the word "embedding" is used in the strict meaning of non-crossing embedding, but we prefer to make the distinction between arbitrary embeddings and embeddings where no edges intersect.)
Notice that our definition of embedding does not require straight lines. We could very well draw the graph using curved lines or even squiggles. For example, the previous figure shows three ways to draw the same graph: non-planar and planar with curved or straight lines. Intuitively, we can always assume straight lines for planar embeddings because if, as in the figure, we have a planar embedding with curved lines, we can always find a way to move vertices around so that all lines end up being straight. This will be our first theorem.
Theorem 1. (Fáry.) If a graph is planar, then it has a planar embedding where all edges are straight lines.
We won’t give a formal proof for this theorem because it involves some notions of topology that fall outside the scope of this book. Suffice it to say that we can, from now on, focus on studying planar embeddings with straight lines and be certain that whatever we discover for them applies to all planar graphs. This gets our first assumption out of the way.
Understanding planar graphs
Before we can answer how to check if a graph is planar, we’ll focus on understanding the basic properties of planarity. By analyzing the necessary conditions, we’ll build valuable intuition about where to look for sufficient ones.
Let’s look at the following planar graph below.
Doesn’t this look exactly like a tetrahedron? It is, and following this analogy, we’ll open up a box of extremely powerful tools inspired by geometry.
Besides vertices and edges, an additional structure rises from this geometric point of view: faces. Intuitively, a face is any (maximal) contiguous region of the plane that does not contain any vertex or edge. In all planar embeddings, we’ll have several internal faces and always exactly one external face.
As an example, the following figure shows an embedding with four faces: each of the three internal faces enclosed respectively by the triplets of vertices {a, b, c}, {a, b, d}, and {a, c, d}; and one external face defined by the frontier of the graph {b, c, d}.
Can we change the number of faces without destroying planarity? Give this a few attempts before you move on.
Euler’s characterization of planar graphs
Welcome back! We also attempted to increase the number of faces, but — like you — we failed. One idea is to split face #1 into two faces by placing a vertex halfway between c and b, adding two edges and one vertex in total. No matter how we try, adding a face always results in a new vertex and two new edges. Similarly, we can merge faces by removing the separating edge.
Is there a pattern? Yes. This will be our next theorem, due to no one else than the greatest mathematician of all times and father of graph theory, Leonard Euler.
Theorem 2. (Euler.) Let G = (V, E) be a connected planar graph, and 𝓔 be a planar embedding. If n = |V| denotes the number of vertices, m = |E| denotes the number of edges, and f denotes the number of faces, then
holds.
Euler’s theorem is quite impressive. There are infinite possible planar embeddings of a single graph, yet the magic formula n - m + f = 2 holds for all of them. Quantities such as this are called invariants, and they are extremely useful throughout pure and applied mathematics. Euler’s theorem is not an exception. Let’s prove it!
Proof. We will use induction in m.
Base case. If m = 0, then the graph must have exactly n = 1 vertex to be connected, and exactly f = 1 face (the external face).
Inductive step. Suppose that m > 1. There are two cases to consider: either G is a tree, or it has at least one loop.
If G is a tree, then it has exactly m = n - 1 edges and f = 1 faces. Thus, n - (n - 1) + 1 = 2 holds as well.
If G has a loop, then we can proceed as follows. Find an edge e in the loop and remove it from G to construct G' = (V, E \ {e}). The new graph G' is still connected because removing a loop edge can never disconnect a graph. Thus, in G' the theorem holds by the inductive hypothesis:
Notice that removing e must have destroyed exactly one face. If e is on the frontier of the embedding, then removing it made one internal face merge with the external face. Otherwise, it merges two internal faces. In any case, we have n' = n, m' = m - 1, and f' = f - 1. Plugging these into the inductive step, we have
which solves to
This is what we had to show. ◼
Even though we haven’t emphasized this in the proof, the number of faces seems to depend on the embedding. After all, they are determined by the points and geometric curves given by the drawing. However, an immediate corollary of Euler’s theorem shows that no matter the (planar) embedding, the number of faces is constant.
Corollary 1. (Invariance of faces.) The number of faces in a connected planar graph is the same for all planar embeddings.
Proof. First, note that the number of edges and vertices are independent of the embedding: |V| = n and |E| = m, regardless of how we draw the graph. Then, for any planar embedding, Euler’s theorem implies that n - m + f = 2, from which f = 2 + m - n follows. ◼
Euler’s theorem is one of the most important characterizations of planar graphs. It will allow us to prove that some fundamental graphs are not planar. But before going there, let’s look at a couple of other powerful properties of planar graphs.
Other properties of planar graphs
How many edges can a planar graph have? Intuitively, the more edges we add, the more likely we encounter an unavoidable edge crossing. Can we make this argument formal?
Theorem 3. (Edges of planar graphs.) If G = (V, E) is planar with order n = |V| ≥ 3, then G has at most m = |E| ≤ 3n - 6 edges.
Proof. Let B be the sum of the number of boundaries in the frontier of each face. (We count each edge as many times as the different faces in which it appears.) Since every edge can at most appear in the frontier of two different faces, B ≤ 2m.
On the other, since each face has at least three edges, then B ≥ 3f. Thus, 3f ≤ 2m, or
f ≤ 2m/3. Applying Euler’s theorem, we obtain
Grouping terms, we get 6 ≤ 3n - m, from which m ≤ 3n - 6 follows. ◼
If the total number of edges is bounded in planar graphs, it follows that some vertices must have a low degree. Otherwise, if all vertices could have an arbitrarily large degree, we could have as many edges as we wished. This observation gives us another property of planar graphs.
Theorem 4. In every planar graph G, there is at least one vertex v with deg(v) ≤ 5.
Proof. Let's assume that all vertices have deg(v) ≤ 6, and remember that
Then,
which means 2m ≥ 6n, or m ≥ 3n. But from Theorem 3. we have m ≤ 3n - 6, which is a contradiction. Thus. the assumption is false; that is, at least one vertex must have
deg(v) ≤ 5. ◼
Can we improve the previous result? It seems there is some room for improvement because there is a large gap between 3n—6 and 3n, but a single vertex with deg(v) = 0 is enough to bridge that gap. Thus, we cannot guarantee more than one low-degree vertex in general, although there could be many in a particular graph.
Finally, we’ll claim the following super useful property without proof.
Theorem 5. Let G a planar graph. Then for every vertex v, there is always at least one embeddding where v is in the frontier.
Proof. (Sketch.) Instead of working on the Euclidean plane ℝ², let’s move up into the space ℝ³! Recall our tetrahedron example earlier? It turns out that every planar graph can be obtained as a two-dimensional projection of a three-dimensional convex polyhedron. In other words, you can obtain a planar representation by picking up the wireframe of the convex polyhedra and taking a photo.
Now, mentally highlight the vertex v on your polyhedral representation. We can rotate the polyhedra until the highlighted vertex appears on the frontier and take the photo in that instance. This way, we have obtained the desired planar embedding. ◼
Theorem 5. will be useful in future theorems when we want to remove one specific vertex to make an inductive proof work.
Armed with Euler’s characterization and the rest of the properties we have discovered in this section, we are ready to tackle our first problem: determining whether an arbitrary graph is planar.
When is a graph planar?
Let's tackle the two basic cases of non-planar graphs that appear over and over: K₅ and K₃,₃.
Intuitively, these graphs have too many edges and too few vertices. If we try to draw them in a plane, we will find there is always one edge we cannot avoid crossing. We will use Euler's theorem to formalize this idea and arrive at a contradiction.
The general form of the proofs will be the following. Using Euler's characterization, we will first determine the number of faces any planar embedding of the graph should have. Then, just as we did in Theorem 3, we will count how many edges should surround each face. This will give us two different ways to connect edges and faces, and we will reach a contradiction.
Let's start with K₅.
Theorem 6. K₅ is not planar.
We'll prove by contradiction; let's assume that K₅ is planar. By Euler's theorem, it must have -5 +10 + 2 = 7 faces. Since each face must be surrounded by at least three edges, we have B ≥ 3f. (Recall that B denotes the total number of boundaries.) On the other hand, by the same reasoning of Theorem 3, since each edge appears in at most two faces, B ≤ 2e.
This gives us
This implies 21 ≤ 20, which is a contradiction. Thus, K₅ cannot be planar. ◼
The proof for K₃,₃ is very similar, hinging on a critical observation about the nature of bipartite graphs: in every bipartite graph, the smallest cycle has at least four edges.
With this in our hands, let’s tackle the non-planarity of K₃,₃.
Theorem 7. K₃,₃ is not planar.
Proof. Again, assume that K₃,₃ is planar. Since K₃,₃ has n = 6 vertices and m = 9 edges, Euler's formula yields -6 + 9 + 2 = 5 faces. By a reasoning similar to the K₅ case, the total number of boundaries must be B ≥ 4f (as cycles in a bipartite graph have at least four edges), while B ≤ 2m. Thus, we get,
implying that 20 ≤ 18, which is a clear contradiction. ◼
This is a powerful strategy that we can use to prove many graphs are not planar. In general, it involves the following steps:
Assume that G is planar.
Apply Euler’s theorem to determine the supposed number of faces f.
Find the length of the smallest cycle, and call it g (for girth).
Establish the inequality gf ≤ 2m.
Find a contradiction.
However, if you can’t manage to find a contradiction, that doesn’t mean the graph is planar! It just means you can’t disprove it. To find a necessary and sufficient condition for planarity, we must dig deeper.
Graph subdivisions
Intuitively, we can see that if any graph contains a non-planar subgraph, the whole graph must also be non-planar, right? Thus, if we find, for example, K₅ or K₃,₃ lurking inside a bigger graph, we can cross that graph as non-planar for good! However, what are the odds we'll find exactly K₅ or K₃,₃ as a subgraph on a random non-planar graph? Incredibly, the odds are pretty high.
It turns out that every non-planar graph has something resembling either K₅ or K₃,₃, but it is not as simple as finding these exact subgraphs. Instead, we must look for a subdivision. So, let's back up a bit.
Definition 3. (Graph subdivisions.) Given a graph G, a subdivision G' of G is any graph that can be formed by successively subdividing an arbitrary edge xy — i.e., adding a new vertex v replacing the edge xy for the two edges xv and vy.
Let's visualize that for a moment. The following illustration shows a simple graph G and three consecutive modifications that create subdivisions of G. We start with K₅, insert a vertex x in the edge ab, and then insert another vertex y in edge cd.
The crucial result to consider is that subdividing edges this way does not change the planarity of any graph. Why? Intuitively, all we can achieve by subdividing an edge indefinitely is to transform a straight line into a curve. Still, we already know that curved edges don't give us any advantage. Let's state this in a lemma.
Lemma 1. Let G be a graph and G' be its subdivision. Then G is planar if and only if G' is also planar.
This means that any subdivision of K₅ (like the ones shown before) is also non-planar. That, in turn, means any graph that has a subgraph that can be obtained as a subdivision of K₅ is thus non-planar. The same is true for K₃,₃. Now we can give this concept a name.
Definition 4. (Topological minors.) We say that H is a topological minor of G if there exists a subdivision of G that has H as a subgraph.
Reformulating the previous observation, we obtain the following proposition.
Theorem 8. Let G be an arbitrary graph. If G is planar, then K₅ or K₃,₃ is not its topological minor.
Theorem 8 is a necessary condition of planarity: not having K₅ or K₃,₃ is necessary to be planar. Is this sufficient? In other words, is G planar if you cannot find either K₅ or K₃,₃ as its topological minor?
Buckle up. Here is the greatest result in the theory of planar graphs that has ever been conceived. (Well, this and the four-coloring theorem.)
Theorem 9. (Kuratowski.) A graph is planar if and only if it doesn't contain K₅ or K₃,₃ as a topological minor.
Wait, what!? Yes, that's right. Every non-planar graph has a subdivision of either K₅ or K₃,₃ somewhere hidden inside its guts. In a sense, these two are the only original non-planar graphs. All the rest are just remixes.
Planarity testing
Now that we have a theorem, two questions remain. The first is whether we can turn this into an algorithm for efficient planarity testing. A theorem is good and all, but if we have to check all possible subgraphs to see if any of them is a subdivision of K₅ or K₃,₃, then the theorem is pretty much worthless, at least for our purposes of building the Major's new supercomputer.
On the other hand, let's say we have an algorithm for planarity testing and confirm our circuit is planar. That is still not enough! We need a way to actually lay out the components — that is, we need an algorithm to build planar embeddings.
But that's a topic for another day.
This post was a collaboration with Alejandro, taken directly from our upcoming book, The Hitchhiker's Guide to Graphs. This project grew out of our series in graph theory here, aiming to focus on the algorithmic aspects as well. We'll even implement our custom graph library from scratch.
The book is already available in early access, with instant updates to the content as we write it.
If you would like to see what's the book like, check out our introductory series on graph theory:
 | A guest post by
|
Building a bit of hype on top of that connection between planar graphs and solid geometry, we may or may not have an upcoming secret post going deeper into that idea. 🔥🔥