Crossing Number

From the intricate wiring of a microchip to the vast web of social networks, we live in a world defined by connections. When we attempt to visualize these networks, we inevitably face a practical problem: lines must cross. Each crossing can represent a point of failure, a source of confusion, or a physical cost. This raises a fundamental question: what is the minimum number of crossings we are forced to accept? The mathematical answer lies in the concept of the ​​crossing number​​, a powerful measure of a network's intrinsic complexity. This article explores the depths of this seemingly simple idea.

First, we will delve into the ​​Principles and Mechanisms​​ that govern the crossing number. We will start with the foundational principles of planar graphs, using Leonhard Euler's famous formula to understand why some networks simply cannot be drawn flat. This will lead us to the powerful Crossing Number Inequality, a tool that provides a guaranteed lower bound on the complexity of any network design. Then, in ​​Applications and Interdisciplinary Connections​​, we will witness how this theoretical concept becomes a practical tool. We will see how minimizing crossings brings clarity to biological data, how the difficulty of computing the crossing number has profound implications in computer science, and how it can be used to solve problems in seemingly unrelated fields like geometry and topology.

Imagine you're an engineer laying out the wires on a circuit board, or a city planner designing a subway system. Your goal is to connect a set of points, but you live on a flat surface—a plane. Sooner or later, you'll face an annoying problem: your paths have to cross. Each crossing is a point of failure, an expensive bridge, or a source of signal interference. The question that naturally arises is not if we will have crossings, but how many we are forced to accept. This simple, practical puzzle is the gateway to a deep and beautiful area of mathematics known as topological graph theory, and its central character is the ​​crossing number​​.

Let's start with a game. Can you connect three houses to three utilities—gas, water, and electricity—without any of the pipes or wires crossing? Try it on a piece of paper. You'll find it's maddeningly impossible. This famous puzzle is a drawing of the graph we call $K_{3,3}$. Now, what if we tweak the numbers? Imagine designing a circuit with 3 processing units that must all connect to 4 separate memory banks. Or what if you have 5 components on a microchip, and every single one must be able to talk directly to every other one?

In these cases, you are trying to draw what mathematicians call a ​​graph​​—a set of vertices (the components) and edges (the connections)—on a plane. A graph that can be drawn without any edges crossing is called a ​​planar graph​​. Our experience with the utilities puzzle suggests that $K_{3,3}$ is not planar. It turns out that the 5-component system, a graph called the ​​complete graph​​ $K_5$, is also not planar. No matter how cleverly you arrange the vertices or curve the edges, you will always be left with at least one crossing. This isn't a failure of imagination; it's a mathematical fact. But why? What law of nature forbids these simple networks from lying flat?

The answer lies in a stunningly simple formula discovered by Leonhard Euler in the 18th century. For any planar graph drawn on a sheet of paper (and connected in one piece), if you count the number of vertices ($v$), edges ($e$), and the regions or "faces" ($f$) it divides the paper into (including the infinite region outside), you will always find that:

This is ​​Euler's formula​​. It's a universal law for all planar graphs, as fundamental to them as $E=mc^2$ is to physics. It doesn't care about the size or shape, only the connection topology. Now, how does this help us with crossings?

Let's think about the faces. In a simple graph (no loops or multiple edges between the same two vertices), every face must be bounded by at least 3 edges. If we sum the number of edges around each face, we get a total of at least $3f$. Since each edge borders exactly two faces, this sum is also exactly $2e$. So, we have $3f \le 2e$.

Now for the magic. We can use Euler's formula to get rid of $f$. Since $f = 2 - v + e$, we can substitute this into our inequality:

A little bit of algebra rearranges this into a powerful new law:

This is the key! For any simple graph to even have a chance of being planar, the number of its edges cannot grow too quickly compared to its vertices. It's a strict budget.

Let's test this on our 5-component system, $K_5$. It has $v=5$ vertices. Since every component connects to every other, it has $e = \binom{5}{2} = 10$ edges. Let's check the budget: is $10 \le 3(5) - 6$? The right side is $15-6=9$. The inequality becomes $10 \le 9$, which is false!. The graph $K_5$ breaks the law of planarity. It has too many edges for its number of vertices. It simply cannot be drawn flat. This proves that at least one crossing is absolutely necessary. And since we can easily draw it with just one crossing (try drawing a pentagon with a star inside), we know the minimum is exactly one. The ​​crossing number​​ of $K_5$, denoted $cr(K_5)$, is 1.

This is wonderful for proving a graph isn't planar, but what about quantifying how non-planar it is? If a network design for a high-performance computer has 50 processors and 220 connections, how many crossovers are we stuck with?

We can brilliantly extend our planarity law. Take any drawing of a graph $G$ with $v$ vertices and $e$ edges. Let's say it has $C$ crossings. We can turn this into a new, planar graph, let's call it $G'$, by a simple trick: place a new vertex at every single crossing point. Each crossing involves two edges. By putting a vertex in the middle, we split each of those two edges into two smaller edges. So, for each crossing, we add 1 vertex and 2 edges.

The new graph $G'$ is planar by construction. It has $v' = v + C$ vertices and $e' = e + 2C$ edges. Since $G'$ is planar, it must obey the law we just discovered: $e' \le 3v' - 6$. Let's substitute what we know about $G'$:

Solving this for $C$, we arrive at the magnificent ​​Crossing Number Inequality​​:

This tells us that for any drawing, the number of crossings $C$ must be at least $e - 3v + 6$. Therefore, the absolute minimum number of crossings, the crossing number $cr(G)$, must also obey this bound.

For that computer network with $v=50$ and $e=220$, we can now give the engineers a guaranteed lower bound on their problem. The number of crossings must be at least $220 - 3(50) + 6 = 220 - 150 + 6 = 76$. Any layout they ever produce will have at least 76 crossings. This is incredibly powerful; we know something fundamental about the design's complexity without ever trying to draw it! Applying this to a 9-node fully-connected network ($K_9$) similarly guarantees at least $36 - 3(9) + 6 = 15$ crossings.

Knowing the crossing numbers of small, fundamental graphs like $K_5$ allows us to reason about larger, more complex ones. Consider the complete graph on 6 vertices, $K_6$, which might model a 6-hub computing module. How many crossings must it have?

Let's try a clever counting argument. Take any drawing of $K_6$. If you remove any single vertex and its attached edges, you are left with a drawing of $K_5$. We already know that any drawing of $K_5$ must have at least one crossing. Since we can remove any of the 6 vertices to get a $K_5$, it seems like we should have at least 6 crossings. But we must be careful—we are overcounting! A single crossing in the original $K_6$ drawing involves four vertices. It will remain in the drawing when we remove either of the other two vertices. So, each crossing in $K_6$ is counted exactly twice in our procedure. Therefore, the total number of crossings in $K_6$ must be at least $\frac{6}{2} = 3$.

This gives us a lower bound: $cr(K_6) \ge 3$. Can we achieve it? Yes! A beautiful, symmetric drawing exists (based on a triangular prism) that has exactly 3 crossings. Thus, we have pinned the exact value: $cr(K_6) = 3$.

This building-block principle also works in other ways. If you take a $K_5$ and a $K_{3,3}$ and merge them by identifying a single vertex from each graph, the complexity simply adds up. The crossing number of the combined graph is just $cr(K_5) + cr(K_{3,3}) = 1 + 1 = 2$. It’s as if the two tangled messes can be kept in their own "zones," meeting only at one point, so their complexities don't interfere with each other.

You might now be thinking: "This is great! Is there a formula for the crossing number of any graph?" The honest and exciting answer is: no. Finding the crossing number is fantastically difficult. In fact, it's a famous ​​NP-hard​​ problem, a term computer scientists use for problems where finding a solution seems to require a brute-force search of astronomical size, even though checking a proposed solution is easy. If someone hands you a drawing of a graph, you can just count the crossings. But to find the best drawing? That's hard.

How hard? Imagine you have a magical machine, an oracle, that can instantly tell you if a graph can be drawn with at most $k$ crossings. Even with such a device, to find the exact crossing number of $K_{10}$, you would still need to make at least 8 calls to it, using an efficient binary search strategy to narrow down the possibilities.

For some very structured families of graphs, mathematicians have beautiful conjectured formulas that seem to hold true for all tested cases, but a complete proof remains just out of reach. For the complete graphs $K_n$ and complete bipartite graphs $K_{m,n}$, these formulas predict an explosion in complexity. For instance, the conjectured formulas tell us that a 10-core system ($K_{10}$) should have 60 "faults" (crossings), while a 13-core system ($K_{13}$) would have a staggering 225. For a system with 5 processors and 11 memory modules ($K_{5,11}$), the number of unavoidable interferences is conjectured to be 100.

This is where the journey of discovery stands today. We have fundamental principles, like Euler's formula, that provide a bedrock of understanding. We have powerful tools, like the crossing number inequality, that give us concrete guarantees. And we have open frontiers, filled with elegant conjectures and deep computational questions, reminding us that even in the simple act of drawing lines on paper, there are universes of complexity waiting to be explored.

We have spent some time understanding the machinery behind the crossing number—what it is and how we might, in principle, calculate it. But what is it for? Why should we care about how many times lines cross in a drawing? The answer, it turns out, is wonderfully broad. The seemingly simple notion of a crossing is a thread that ties together the practical art of data visualization, the abstract world of computational theory, and even the topological structure of knots and braids. It is a concept that is at once a practical nuisance to be minimized and a profound theoretical tool to be wielded. Let us embark on a journey to see where this idea takes us.

Imagine you've been handed a giant, tangled ball of yarn. Your task is to understand how it's connected. Is it one long piece? A dozen smaller, intertwined loops? This is precisely the challenge faced by scientists in countless fields, from sociologists mapping social networks to engineers designing circuit boards. Nowhere is this challenge more apparent than in modern biology.

A systems biologist might have data on thousands of proteins and the interactions between them. Simply listing these interactions is a meaningless wall of text. The first instinct is to draw a picture: a graph where proteins are dots (nodes) and interactions are lines (edges). But an arbitrary drawing is likely to look like our tangled yarn—a chaotic mess of overlapping lines that reveals nothing. The art of network visualization is the art of untangling this mess, and a key principle of this art is the minimization of edge crossings.

One of the most elegant and effective methods for this is the "force-directed" layout. Imagine each protein-node is a charged particle, repelling every other particle. Now, imagine that each edge—each interaction—is a tiny spring pulling its two connected proteins together. If you let this system go, it will jiggle and shake until it settles into a low-energy state. What does this state look like? Densely interconnected groups of proteins, which often correspond to "functional modules" in the cell, are pulled into tight spatial clusters by their many internal springs. Meanwhile, the global repulsion pushes these clusters apart from one another. The result is a map where the network's community structure becomes immediately visible. While the algorithm doesn't explicitly count and minimize crossings, its physical analogy of minimizing potential energy naturally produces drawings that are far clearer and have far fewer crossings than, say, arranging all the nodes in a simple circle.

This quest for clarity extends to more structured diagrams. Consider the drawing of a family tree, or pedigree. Geneticists have strict conventions for these drawings: individuals are arranged in generational layers, and spouses are placed side-by-side. Even within these rules, we have choices about the left-to-right ordering of individuals in each generation. A poor choice can lead to a confusing web of crisscrossing lines of descent. A good choice, which minimizes these crossings, makes the inheritance patterns clear at a glance. The problem of finding the best ordering is a direct application of crossing number minimization under constraints. The same principle applies to visualizing complex biochemical pathways, where molecules in different cellular compartments must be laid out to make the flow of reactions understandable. In these cases, we see that the crossing number isn't just an aesthetic preference; it is a fundamental measure of a diagram's explanatory power.

As we've just seen, minimizing crossings is a powerful tool. This naturally leads to a computational question: can we write a program that finds the drawing with the absolute minimum number of crossings for any graph? The answer, unfortunately, is almost certainly no. Determining the crossing number of a graph is a famously difficult problem in computer science—it is NP-hard. This means that for large, complex graphs, no known algorithm can find the optimal solution in a reasonable amount of time.

This difficulty is not just a theoretical curiosity; it has practical implications. In computational complexity theory, researchers often try to prove that one problem is "as hard as" another. A common technique is to transform a hard problem on a general graph into a supposedly simpler problem on a planar graph (a graph with crossing number zero). A natural way to do this is to take a drawing of the general graph and replace each edge crossing with a small, cleverly designed planar "gadget."

But here lies a trap, illuminated by the very concept of the crossing number. Imagine we have a problem for which we know it's hard to tell the difference between a "YES" instance and a "NO" instance (a property called a "hardness of approximation gap"). When we apply our gadget-based reduction, the size of the new problem depends on the number of crossings in our original drawing. If our hard instances require a large number of crossings, the gadgets we add might overwhelm the original structure. In one such hypothetical scenario, the cost of eliminating crossings by adding gadgets is so high that the crucial gap between "YES" and "NO" instances shrinks and vanishes as the problem size grows. The reduction becomes useless. The lesson is profound: the crossing number is not just a property of a drawing, but an intrinsic measure of a graph's complexity that can fundamentally limit how we can manipulate it algorithmically.

So far, we have treated crossings as an enemy to be vanquished. But in a beautiful twist of intellectual judo, mathematicians realized that the inevitability of crossings in dense graphs could be turned into a powerful weapon. This idea is crystallized in the ​​Crossing Number Lemma​​. It gives us a simple, stunning guarantee: if a graph has significantly more edges than vertices, it doesn't just have crossings—it must have a lot of them. Specifically, for a graph with $v$ vertices and $e$ edges where $e \ge 4v$, the crossing number $cr(G)$ is at least on the order of $e^3/v^2$.

What can we do with such a weapon? We can solve problems that seem to have nothing to do with graph drawing. Consider a classic question from combinatorial geometry: you have $n$ points and $m$ lines in a plane. What is the maximum number of times these points can lie on these lines (the number of "incidences")?

The brilliant insight of Szemerédi and Trotter was to reframe this geometric puzzle as a graph theory problem. Let the $n$ points be the vertices of a graph. The lines are not edges themselves. Instead, the segments of lines between consecutive points become the edges. The total number of edges in this graph is the total number of incidences, $I$, minus the number of lines, $m$. The number of vertices is simply $n$. Now, any two edges in this drawing can cross only if their corresponding lines intersect. Thus, the number of crossings in our graph drawing is at most the total number of intersection points between the lines.

By applying the Crossing Number Lemma to this graph, we get a lower bound on the number of crossings in terms of edges ($I-m$) and vertices ($n$). But we also have an upper bound on the crossings from the geometry of the lines. Playing these two bounds against each other yields a remarkably tight and non-obvious upper bound on the number of incidences, $I$. A purely geometric question is answered by reasoning about the inevitability of tangled drawings. This is a masterclass in the unity of mathematics, where a concept from one field provides the key to unlock a door in another.

Our journey now takes us to a realm where tangles are not just a feature of a drawing, but the object of study itself: knot theory. A knot is, mathematically, a closed loop embedded in three-dimensional space. Its projection onto a plane—a knot diagram—is what we draw, and its crossings are its defining feature. Here, we don't want to eliminate crossings, because doing so would change the knot itself, like untying a shoelace.

The number of crossings is the most basic measure of a knot's complexity. But the connections run deeper. Consider the property of tricolorability. It’s a simple game: you try to color the arcs of a knot diagram with three colors, subject to a simple rule at each crossing: the three arcs meeting there must either be all the same color or all different colors. For the coloring to count, you must use at least two colors. It turns out that whether a knot is tricolorable is a topological invariant—it doesn't depend on the specific diagram, but on the knot itself. And it connects directly to the crossing number: one can prove that for a knot diagram to be tricolorable, it must have at least three crossings. A simple coloring game reveals a fundamental geometric constraint!

This connection between crossings and algebraic properties becomes even more striking when we consider braids. A braid can be thought of as a set of strands flowing from top to bottom, weaving over and under each other. Braids form a rich algebraic structure called a braid group, and they have surprising applications, from modeling particle exchange in quantum physics to cryptography. Each braid corresponds to a permutation, describing how the final positions of the strands are shuffled relative to their starting positions. The connection is breathtakingly simple: the parity of this permutation (whether it's even or odd) is determined by the total number of crossings in the braid's diagram. If the number of crossings, $C$, is even, the permutation is even. If $C$ is odd, the permutation is odd. This can be expressed by the elegant formula $\text{sgn}(\pi) = (-1)^C$. A simple count of geometric crossings in a diagram dictates a fundamental algebraic property of an operator that could be acting on quantum states.

Finally, let us ask one last question. What if we abandon all attempts at design and optimization? What if we simply create a tangle at random and see what happens? Imagine placing $2n$ points on a circle and then randomly pairing them up to form $n$ chords. How many times would we expect these chords to cross? Using the power of indicator variables and linearity of expectation, one can derive a beautifully simple answer: the expected number of crossings is exactly $\frac{n(n-1)}{6}$. There is an inherent, predictable order even in this random arrangement.

From the practical layouts of biological data to the deep abstractions of algebra and topology, the humble crossing number has proven to be a concept of remarkable power and reach. It teaches us that how things are drawn matters, that complexity has a price, and that sometimes, the best way to understand a system is to count the ways it gets tangled up.