Graph Thickness

In fields from computer science to biology, we often encounter networks so tangled they seem incomprehensible. How can we manage the complexity of a circuit board, a social network, or a protein interaction map where connections cross and overlap chaotically? This article addresses this challenge by introducing the powerful concept of ​​graph thickness​​, a mathematical tool for deconstructing complexity. It offers a way to measure the intrinsic "layeredness" of any network, revealing hidden order beneath the chaos. This article will guide you through the core ideas behind this concept. First, in "Principles and Mechanisms," we will explore the fundamental definition of thickness, its relationship to planar graphs, and the mathematical formulas used to estimate it. Then, in "Applications and Interdisciplinary Connections," we will see how this abstract idea provides concrete solutions and deep insights into fields like electronics, network architecture, and even the fundamental limits of system design.

Imagine you are given a hopelessly tangled ball of yarn, representing a complex network of connections—perhaps a social network, a computer chip's wiring, or the intricate web of protein interactions in a cell. Your first instinct might be to despair. How can you possibly understand a system where everything seems to be connected to everything else in a chaotic jumble of crossings and overlaps?

This is a fundamental challenge in science and engineering. But what if you could untangle this mess not by cutting the strings, but by revealing a hidden, orderly structure within? What if you could discover that this complex web is actually the superposition of several, much simpler, non-tangled layers? This is the central idea behind ​​graph thickness​​.

The ​​thickness​​ of a graph, denoted by the Greek letter theta, $\theta(G)$, is the minimum number of transparent sheets you would need to draw the entire graph, with the rule that on any single sheet, no lines (edges) are allowed to cross. When you stack these transparent sheets, you see the original, complex graph.

This isn't just an abstract mathematical game. It has profound practical implications. Think of a modern printed circuit board (PCB). To connect thousands of components in a small space, engineers can't just draw all the connections on a single surface; the wires would cross and short-circuit. Instead, they use multi-layer boards. The thickness of the corresponding graph tells them the absolute minimum number of layers they would need to build the circuit. Similarly, it can represent the minimum number of frequency channels needed to establish a set of communication links without interference. Thickness, then, is a measure of a network's intrinsic "layered complexity."

Let's start with the simplest case. What does it mean for a graph to have a thickness of one? It means the entire graph can be drawn on a single sheet without any edges crossing. We have a special name for such graphs: they are called ​​planar graphs​​.

This connects thickness to another, perhaps more intuitive, concept: the ​​crossing number​​. The crossing number, $cr(G)$, is the minimum number of intersections you get when you try to draw a graph on a flat plane. If a graph is planar, you can draw it with zero crossings, so $cr(G) = 0$. If its thickness is one, it is, by definition, planar. These two statements are perfectly equivalent: a graph has $\theta(G)=1$ if and only if $cr(G)=0$. They are two sides of the same coin, describing the ideal state of graphical simplicity.

You can't always judge a book by its cover. Some graphs that look complicated are, in fact, perfectly planar. Consider the graph of a triangular prism, with two triangular faces connected by three edges. At first glance, it seems dense. But with a little cleverness—drawing one triangle inside the other and connecting the corresponding corners—you can draw it perfectly on a single sheet with no crossings. Its thickness is one.

Most interesting networks, however, are not planar. The complete graph $K_5$ (five points with every point connected to every other) is a classic example. No matter how you try, you cannot draw it without at least one crossing. So, its thickness must be greater than one. But is it two, three, or a hundred?

Here, mathematics gives us a powerful, if blunt, instrument. A famous result stemming from Euler's work on polyhedra tells us that planar graphs are "sparse." They can't have too many edges for their number of vertices. Specifically, a simple planar graph with $v$ vertices (where $v \ge 3$) can have at most $3v-6$ edges.

This simple inequality is a key. If your graph has $m$ edges and you want to decompose it into $t$ planar layers, then each layer can contribute at most $3v-6$ edges to the total. Therefore, the total number of edges, $m$, must be less than or equal to $t \times (3v-6)$. Rearranging this gives us a wonderful formula for a lower bound on the thickness:

The ceiling brackets $\lceil \dots \rceil$ mean we round up to the nearest whole number, since thickness must be an integer.

Let's see this yardstick in action. Imagine a network of 11 sensors, all connected to each other ($K_{11}$). This graph has $v=11$ vertices and $m = \binom{11}{2} = 55$ edges. Plugging this into our formula:

Instantly, we know that it's impossible to design this network on two layers; we need at least three. But be careful! This is a lower bound. It tells us the floor, but the ceiling might be higher. For the complete graph on 9 vertices, $K_9$, the formula gives a lower bound of $\theta(K_9) \ge \lceil \binom{9}{2} / (3 \cdot 9 - 6) \rceil = \lceil 36/21 \rceil = 2$. However, the actual thickness of $K_9$ is known to be 3. Our yardstick provides a valuable first estimate, but it doesn't always tell the whole story.

Can we refine our yardstick? Yes, if we look more closely at the graph's internal structure. The $3v-6$ rule applies to any planar graph. But some types of graphs have even stricter rules.

Consider a ​​bipartite graph​​, which is a graph whose vertices can be split into two sets, say 'reds' and 'blues', such that every edge connects a red vertex to a blue one. There are no edges connecting two reds or two blues. A consequence of this structure is that bipartite graphs cannot contain cycles of odd length (like triangles). This absence of triangles makes them even sparser than general planar graphs. A planar bipartite graph with $v$ vertices can have at most $2v-4$ edges.

Let's apply this sharper tool to the 4-dimensional hypercube graph, $Q_4$. This graph has vertices representing the 16 corners of a hypercube ($v=16$) and edges connecting corners that differ in just one coordinate ($m=32$). The hypercube is bipartite (you can color the vertices based on whether they have an even or odd number of '1's in their binary representation).

If we blindly used the general formula, we'd get $\theta(Q_4) \ge \lceil 32 / (3 \cdot 16 - 6) \rceil = \lceil 32/42 \rceil = 1$, which is a trivial and unhelpful bound. But because we recognized its bipartite nature, we can use the stronger inequality:

By understanding the graph's structure, we've proven it's non-planar and needs at least two layers. This is a beautiful example of how deeper knowledge yields greater insight.

Thickness is just one way to describe the geography of the vast, non-planar world. How does it relate to other explorers' maps?

• ​​Thickness vs. Arboricity:​​ The ​​arboricity​​, $a(G)$, is the minimum number of forests (graphs with no cycles) needed to form the graph. Every forest is planar, so any decomposition into forests is also a decomposition into planar layers. This gives us a simple, elegant hierarchy: for any graph, $\theta(G) \le a(G)$. The thickness can never be more than the arboricity. For $K_9$, for instance, the thickness is 3, while its arboricity is 5.

• ​​Thickness vs. Genus:​​ The ​​genus​​, $\gamma(G)$, tells us the simplest surface (a sphere with some number of "handles," like a donut) on which the graph can be drawn without crossings. A planar graph has genus 0. A graph that can be drawn on a donut has genus 1. You might wonder: if a graph has thickness 2, can it always be drawn on a single donut? It seems plausible that two simple planar layers could be cleverly stitched together on a slightly more complex surface. But the answer is a surprising no! There are graphs, such as the complete 4-partite graph $K_{3,3,1,1}$, that have a thickness of 2 but require a surface with two handles (genus 2) to be drawn without crossings. Being "two-layered" is fundamentally different from being "drawable on a donut."

• ​​Thickness vs. Coloring:​​ Here we find the most astonishing disconnect. The famous Four Color Theorem states that any planar map (or graph) can be colored with at most four colors such that no two adjacent regions share a color. So, if a graph has thickness 2, it's made of two planar pieces. Can't we just color each piece with 4 colors and somehow combine them to get a coloring for the whole graph with, say, 8 or 16 colors? Perhaps the whole graph doesn't need many colors? Nature again says no, in spectacular fashion. Consider the complete graph $K_8$, with 8 vertices all connected to each other. It has a thickness of 2. But to color it, you need 8 distinct colors, because every vertex is connected to every other vertex. The fact that it can be split into two "simple" (planar) layers does absolutely nothing to simplify its coloring problem. The local simplicity of the layers does not imply global simplicity for coloring.

We have a definition. We have tools to find lower bounds. But how do we find the exact thickness? This turns out to be an incredibly difficult problem.

You might propose a simple, ​​greedy algorithm​​: start with your first transparent sheet. Go through all the edges of your graph one by one. If an edge can be added to the current sheet without causing a crossing, add it. When you can't add any more edges, put that sheet aside and start a new one with the remaining edges. Repeat until all edges are placed. Seems logical, right?

But this intuitive strategy can fail. It can be short-sighted. Consider $K_8$ again, for which the true thickness is 2. By following a specific greedy procedure, it's possible for the algorithm to pack the first layer in such a "selfish" way that it leaves the remaining edges in a tangled mess that requires two more layers to sort out. The algorithm would incorrectly report a thickness of 3.

This reveals a profound truth. Finding the true thickness isn't just about following a simple procedure; it's about finding a globally optimal, cooperative arrangement among all the layers simultaneously. The simple, elegant definition of thickness hides a vast computational complexity. It's a perfect microcosm of science: the principles can be beautiful and easy to state, but applying them to find the true, optimal answer can be one of the hardest and most rewarding challenges there is.

After our journey through the principles and mechanisms of graph thickness, you might be left with the impression that this is a rather abstract, niche corner of mathematics. Nothing could be further from the truth. Like so many profound ideas in science, the concept of thickness, once understood, reveals itself to be a powerful lens for understanding the structure and limitations of the world around us. It is not merely a question of how to draw a graph; it is a question of how to organize complexity. Let’s explore where this seemingly abstract idea makes its mark.

Look at the device you are using to read this text. At its heart lies a Printed Circuit Board (PCB) or a Very-Large-Scale Integration (VLSI) chip, a marvel of miniature engineering. These are, in essence, layered cities, with components as buildings and conductive traces as highways. The single most important traffic rule in this city is absolute: on any given layer, no two highways can cross. A crossing would mean a short circuit, a catastrophic failure.

Now, imagine you are a design engineer tasked with building a new processing unit with several terminals, where the design requires every single terminal to be directly connected to every other one. You start to lay out these connections on a single layer. You draw a few, then a few more, and very quickly you run into a problem. You become trapped. To add the next required connection, you find you must cross a line you've already drawn. The network is simply too dense, too "tangled," to exist on a single two-dimensional plane.

Your solution is intuitive: you add another layer. You route some of the connections on the first layer and the remaining ones on a second, separate layer, ensuring no crossings on either. The question that saves your company millions in manufacturing costs is this: what is the absolute minimum number of layers required? You have just, without realizing it, asked to compute the ​​thickness​​ of your circuit's graph. For a circuit with 7 fully interconnected terminals (a complete graph $K_7$), a simple calculation shows that the density of connections exceeds what a single planar layer can handle. A careful decomposition, however, shows that two layers are perfectly sufficient. Graph thickness is not just a puzzle; it is a fundamental design constraint that dictates the physical complexity, feasibility, and cost of the electronic circuits that power our civilization.

The challenge of routing connections without crossings extends far beyond the confines of a single microchip. Consider the massive parallel computers that model our climate or discover new drugs. These supercomputers contain thousands of processors that must communicate with each other efficiently. The wiring diagram for these processors often forms a complex network, such as a ​​toroidal grid​​, where processors are arranged in a grid that wraps around at the edges, like the surface of a donut.

Such a grid is demonstrably non-planar; you cannot draw it on a flat sheet without crossings. Yet, understanding its thickness tells us how to build it in the real world. For instance, a toroidal grid like the $C_6 \times C_6$ graph, while non-planar, has a thickness of exactly two. This means its entire complex connection scheme can be perfectly implemented across just two parallel communication layers, a vital insight for network architects.

The concept also helps us understand how complexity emerges. Imagine an existing, well-behaved planar network—perhaps a simple distribution system. What happens if we add a new central "hub" or "apex" vertex and connect it to every single node in the original system? Even if the original network was simple, this single, highly-connected new element can dramatically increase the system's "tangledness," often forcing its thickness to jump from one to two. This is a mathematical reflection of a common real-world phenomenon: introducing a central control or observation point into a simple system can fundamentally increase the complexity of its underlying structure.

Perhaps the most surprising application of graph thickness comes from a thought experiment that reveals a deep truth about systems and their complements. Imagine two competing telecommunications companies, AlphaCom and BetaNet, tasked with providing fiber-optic links to a set of $n$ cities. The contract has a peculiar rule: first, AlphaCom builds its network, connecting any pairs of cities it chooses. Then, BetaNet must build its network by connecting precisely those pairs of cities that AlphaCom did not connect. Between them, they form a complete network ($K_n$), but their individual networks, $G$ and its complement $\bar{G}$, are mutually exclusive.

Both companies want their network to be "efficiently routable," which, for our purposes, means it must be planar. A non-planar network is a logistical nightmare of signal interference and expensive hardware. The question is, can both companies always succeed?

For a small number of cities, say $n \le 8$, it is possible for AlphaCom to design its network $G$ so cleverly that both $G$ and BetaNet's resulting network $\bar{G}$ are planar. But a remarkable mathematical certainty emerges when the number of cities reaches nine. For $n=9$, it is impossible. No matter what network design AlphaCom chooses, at least one of the two companies will be forced to build a non-planar network. This is because the thickness of the complete graph on nine vertices, $\theta(K_9)$, is three. It is impossible to decompose $K_9$ into two planar parts. This powerful result tells us that for a system of even modest size, a certain level of structural complexity (non-planarity) is not just possible, but unavoidable. It's a fundamental limit on our ability to keep interconnected systems simple.

In science, the most fruitful concepts are those that connect to a web of other ideas, and thickness is no exception. It is part of a family of measures that all try to quantify the elusive notion of "how tangled is this graph?"

One close cousin is the ​​crossing number​​, which asks a different question: If you are forced to draw a graph on a single plane, what is the minimum number of edge crossings you must have? The two concepts are deeply related. If a graph has a thickness of one, its crossing number is zero. What if a graph's thickness is greater than two, like our friend $K_9$? This means you cannot decompose it into two planar layers. Therefore, any attempt to split its edges into two sets for drawing on two separate planes must result in at least one of those planes having a non-planar graph on it. This, in turn, guarantees that the total number of crossings on the two planes is at least one. Thickness tells us if we can avoid crossings by layering; crossing number tells us the unavoidable price we pay when we can't.

Another fascinating relative is ​​book thickness​​ (or pagenumber). Imagine all the vertices of a graph are arranged in a line along the "spine" of a book. The edges are then drawn on the "pages," with the rule that no two edges on the same page can cross. The book thickness is the minimum number of pages needed. This is a more constrained layout, relevant to problems in computational biology (like modeling DNA structures) or any system with an inherent linear ordering. An interesting fact is that while all planar graphs have a standard thickness of one, not all of them can be drawn on a single page of a book. Some planar graphs require two pages, revealing that the geometry of our constraints profoundly changes our measure of complexity.

These connections show that thickness is not an isolated curiosity. It is a fundamental measure of structural complexity, a viewpoint that enriches our understanding of how systems are organized, from the logic gates on a chip to the very fabric of mathematical networks. It teaches us that in any complex, interconnected system, the question is not always if we can find a simple representation, but rather, how many layers of simplicity we need to reveal its true nature.