The crossings a graph cannot avoid

Two graphs that will not lie flat proved that the complete graph on five points cannot be drawn without a crossing, by counting edges against faces and finding one edge too many. That settles whether. It leaves how many: when a graph cannot be drawn flat, what is the fewest crossings any drawing of it can have?

The number is the graph’s crossing number, and for the complete graphs it grows startlingly fast. Five points need one crossing. Six need three. Seven need nine. Eight need eighteen — and eighteen only if the edges may curve, because a drawing with straight edges needs nineteen.

The drawing in the figure was not designed; it was searched for. Seven points were scattered and moved one at a time, keeping any move that did not add a crossing, until the count reached nine, which is known to be the minimum. The dots mark the crossings, and every one of them has the same anatomy: two edges that are the diagonals of a quadrilateral whose four corners are points of the drawing.

One crossing for every convex quadrilateral #

That anatomy is the key to straight drawings, and it holds without exception.

Take any four of the points. If they sit in convex position — each outside the triangle of the other three — they form a quadrilateral, and of the six edges joining them exactly one pair crosses: the two diagonals. If one of the four lies inside the triangle of the others, no two of the six edges joining them cross. And two edges can only cross if their four endpoints are distinct, so every crossing belongs to exactly one set of four points. So

$$\text{crossings of a straight drawing of } K_n = \text{number of convex quadrilaterals among the } n \text{ points}.$$

The figure counts both — crossings segment by segment, convex fours by testing each of the $35$ fours among seven points — and requires them to agree before it draws. Minimising crossings of a straight drawing is minimising convex quadrilaterals, which turns a question about drawings into a question about point sets.

And a question about point sets connects to one met before. Every crowd holds a bowl or a dome proved that among enough points in general position some fixed number must be in convex position — five among nine, as the happy-ending problem found. Minimising crossings asks the opposite question for fours: not whether a convex quadrilateral must exist, but how few of them a set can get away with. Among any five points in general position some four are in convex position, which is the smallest case of both statements at once, and it is why the complete graph on five points needs a crossing.

Drawings worth counting #

Before counting crossings it is worth saying which drawings count, because a careless drawing can have as many as it likes and the minimum is taken over careful ones.

A good drawing has three properties: two edges meet at most once, edges from the same point never cross, and no edge crosses itself. Any drawing can be made good without adding crossings. If two edges cross twice, the two pieces between the crossings can be swapped and the crossings removed; if two edges from one point cross, swapping their first stretches out of the point removes the crossing; and a loop in an edge can be cut off. Each move strictly lowers the count, so a drawing with the fewest crossings is automatically good.

That matters for everything that follows. In a good drawing every crossing involves two edges with four different endpoints, which is what lets a crossing be assigned to a set of four points — the straight-line count below, the averaging over smaller graphs, and the sampling argument all rest on it. It is also why the question has the character it does. Five spokes squeezed into $K_5$ showed that whether a graph can be drawn flat depends on which small graphs hide inside it; how many crossings it needs depends on how many such small obstructions it contains and how they overlap, and in the complete graph every four points are a potential one.

Euler’s lower bound, and how weak it is #

A lower bound for any graph comes straight from the argument that made $K_5$ non-planar. A planar graph with $n \ge 3$ points has at most $3n - 6$ edges, by Euler’s formula. Take any drawing of a graph with $m$ edges and remove one edge from each crossing; what is left is planar, so

$$m - \text{cr} \le 3n - 6, \qquad \text{cr} \ge m - 3n + 6.$$

For the complete graph on seven points, with $21$ edges, that gives $6$. The truth is $9$. For eight points it gives $10$ against $18$. For twelve points it gives $36$ against $150$.

The bound is too weak because it is paid only once per crossing. Removing one edge removes every crossing on it, and in a dense drawing an edge carries many crossings, so the $m - 3n + 6$ edges that must go could be removed while only a small fraction of the crossings are paid for. The bound grows like $n^2/2$ for the complete graph, and the truth grows like $n^4$.

Counting crossings by counting smaller graphs #

There is a second way to get more out of a known value, and it is exact where Euler’s bound is slack.

Take the best drawing of $K_n$ and delete one point with its edges; what remains is a drawing of $K_{n-1}$, so it has at least $\text{cr}(K_{n-1})$ crossings. Do this for each of the $n$ points in turn and add up. A crossing involves four points, so it survives the deletion of any of the other $n - 4$, and is counted $n - 4$ times in the total. So

$$(n - 4)\,\text{cr}(K_n) \ge n\,\text{cr}(K_{n-1}), \qquad \text{cr}(K_n) \ge \frac{n}{n-4}\,\text{cr}(K_{n-1}).$$

Starting from the three crossings of $K_6$, it gives at least $7 \cdot 3/3 = 7$ for seven points — short of nine — and from the true value nine it gives $8 \cdot 9/4 = 18$ for eight, which is exact. The same averaging over smaller pieces that the sampling argument performs at random, this performs by deleting every point once; it is weaker as a general tool, because it needs the previous value, and sharper when that value is known. What lifts it to exact values is parity. Daniel Kleitman proved in 1970 that for an odd number of points every drawing of the complete graph in which edges behave sensibly has a crossing count of one fixed parity, so a bound that lands between two admissible values can be pushed up to the next one; with that, Guy completed the values up to ten points.

Sampling turns the square into a fourth power #

The repair is one of the most elegant uses of chance in combinatorics, and it needs nothing beyond Euler’s bound.

Take the best drawing of a graph with $n$ points, $m$ edges and $\text{cr}$ crossings, and keep each point independently with probability $p$, deleting the rest with their edges. The expected number of points kept is $pn$, of edges $p^2 m$ — an edge survives when both its ends do — and of crossings $p^4 \text{cr}$, since a crossing survives only when all four ends of its two edges do. Euler’s bound holds for every sample, so it holds on average:

$$p^4\, \text{cr} \ge p^2 m - 3pn.$$

Now choose $p$. The best choice is $p = 4n/m$, which is at most one when the graph has at least four edges per point, and it gives

$$\text{cr} \ge \frac{m^3}{64\, n^2}.$$

This is the crossing lemma, found independently by Miklós Ajtai, Václav Chvátal, Monroe Newborn and Endre Szemerédi, and by Tom Leighton, in the early 1980s. The weak bound was not wrong; it was being applied to the whole graph at once. Applied to a random piece of the graph, small enough that the piece has few crossings per edge, the one-crossing-per-edge loss stops mattering, and scaling back up multiplies the answer by $1/p^4$ while the edges scale only by $1/p^2$.

On logarithmic axes the difference is a difference of slope. Euler’s bound climbs with slope two; the crossing lemma and the true value both climb with slope four, eight units of $\log$ apart. The sampling bound has the right shape, and a factor of eight is the price of the crude choice of $p$ and of Euler’s constant $3$. The best constant known today is about twice $1/64$, and the true constant for the densest graphs is not known.

What the bound is used for #

A bound that is right up to a constant can be turned into theorems in other subjects, and the crossing lemma’s most famous application is not about drawings at all.

Take $n$ points and $\ell$ lines in the plane, and ask how many point–line incidences there can be. Draw a graph whose vertices are the points and whose edges join consecutive points along each line. Two lines cross at most once, so the drawing has at most $\ell^2$ crossings; a line through $k$ points gives $k - 1$ edges, so there are at least $I - \ell$ edges where $I$ is the number of incidences. The crossing lemma then says $(I - \ell)^3/(64 n^2) \le \ell^2$ whenever there are enough edges, which rearranges to

$$I \le C\left(n^{2/3} \ell^{2/3} + n + \ell\right).$$

That is the Szemerédi–Trotter theorem of 1983, the fundamental bound on incidences, and László Székely found in 1997 that it follows from the crossing lemma in these few lines where the original proof took pages. A statement about points and lines, which mentions no graph, is a consequence of the fact that dense graphs must cross themselves a great deal.

A brick factory, and a proof with a gap #

The question of crossings was first asked about a bipartite graph, and the circumstances are worth recording because they are where the formula in the table comes from.

Pál Turán spent part of the Second World War in a forced-labour camp near Budapest, pushing wagons of bricks from kilns to storage yards on rails that joined every kiln to every yard. Where two tracks crossed, the wagons jumped the rails and spilled their loads, and Turán asked the question the spilled bricks posed: how should the kilns, yards and tracks be laid out to make the crossings as few as possible? With $m$ kilns and $n$ yards that is the crossing number of the complete bipartite graph $K_{m,n}$, and its smallest non-planar case, three and three, is the second of the two graphs that will not lie flat.

Kazimierz Zarankiewicz published a solution in 1954: put the kilns on one axis and the yards on the other, half on each side of the origin, and join them straight, giving

$$\left\lfloor \tfrac m2 \right\rfloor \left\lfloor \tfrac{m-1}2 \right\rfloor \left\lfloor \tfrac n2 \right\rfloor \left\lfloor \tfrac{n-1}2 \right\rfloor$$

crossings, and a proof that no layout does better. The layout is right. The proof was wrong, as Gerhard Ringel and Paul Kainen found in the 1960s, and the formula has been proved only when the smaller side has at most six points. The brick-factory problem is still open, and the formula for complete graphs in this essay is its close relative: the cylindrical drawings of $K_n$ are built on the same idea of splitting the points into two halves that interleave.

Curved edges and straight ones #

The table has two final columns, and they part company at eight points.

For drawings with curved edges the best known drawings of $K_n$ have

$$Z(n) = \tfrac14 \left\lfloor \tfrac n2 \right\rfloor \left\lfloor \tfrac{n-1}2 \right\rfloor \left\lfloor \tfrac{n-2}2 \right\rfloor \left\lfloor \tfrac{n-3}2 \right\rfloor$$

crossings: put half the points on each of two concentric circles and route edges round the cylinder they bound. Richard Guy conjectured around 1960 that no drawing does better, and the conjecture is proved up to twelve points — up to ten by Guy, eleven and twelve by Shengjun Pan and Bruce Richter in 2007.

For straight edges the answer is the convex-quadrilateral count, and from eight points on it is larger: $19$ against $18$ at eight, $62$ against $60$ at ten, $153$ against $150$ at twelve. The difference is a genuine geometric constraint — a straight edge cannot go round the back — and it grows: the straight values are asymptotically about $0.380$ times $\binom n4$, against $0.375$ for the curved ones.

The straight constant is itself a probability. Edward Scheinerman and Herbert Wilf showed in 1994 that it equals the smallest possible chance that four points drawn at random from some distribution in the plane are in convex position — the infimum of Sylvester’s four-point problem over every way of choosing points. Sylvester asked in 1864 for the probability that four random points form a convex quadrilateral and received a different answer from every correspondent, because the answer depends on the region — the same dependence on how random is made precise that the needles dropped on a floor have to be careful about; the crossing number of large complete graphs is the least of all those answers.

On other surfaces, and on chips #

A crossing number depends on the surface the graph is drawn on, and changing the surface changes everything. On a torus the complete graph on seven points needs no crossings at all — the seven regions on a doughnut that all touch one another are that drawing’s dual — and a graph’s crossing number on a surface of genus $g$ falls as $g$ grows, since every handle is a bridge one edge can take over another. The plane is the hardest surface on which to draw anything, and the crossing number measures how hard.

The crossing lemma itself came out of a practical problem. Leighton proved it to bound the area needed to lay out a circuit on a chip, where wires are edges, gates are points, and every crossing costs space; the area of the best layout is tied both to the crossing number and to how few points separate the graph, the quantity the few points that cut a flat graph measured for planar graphs. A graph with many crossings forced on it needs a large chip whatever the designer does, and the fourth power in the crossing lemma is a statement about silicon as much as about drawings.

What the drawings cannot certify #

Every straight drawing here was found by search, and a search proves only an upper bound. The figure reaches $3$, $9$, $19$ and $36$ crossings and stops, because those are the values proved to be minimal by others — by exhaustive enumeration of the ways small point sets can be arranged, which is how the straight values are known up to twenty-seven points and for thirty. The search is evidence that the minimum is achievable; that nothing smaller is achievable is quoted.

No curved drawing is drawn. The cylindrical drawings that realise $Z(n)$ need edges that wind round two circles, and the figures stay with straight lines, whose crossings can be counted exactly. The curved column of the table is Guy’s formula and the proofs of Guy, Pan and Richter, not a computation.

The growth-rate figure plots formulas, not crossing numbers. The top curve is $Z(n)$, which is conjectured and proved only to twelve; the middle one is a bound; neither is a measurement of any drawing.

Still open: the crossing number of the complete graph #

Is the crossing number of $K_n$ exactly $Z(n)$ for every $n$? Guy’s conjecture, sometimes credited to Anthony Hill, has been checked up to twelve points and is open from thirteen. For large $n$ it is known that the true value is at least a large fixed fraction of $Z(n)$, and the fraction has been pushed close to one; no proof of equality is known.

The companion question for straight drawings — the exact constant $0.380\ldots$ — is open too, pinned between bounds that agree to three decimal places. And computing the crossing number of a given graph is hard in general: Michael Garey and David Johnson proved in 1983 that deciding whether a graph can be drawn with at most $k$ crossings is NP-complete, so no efficient method is expected even for graphs of modest size.

A weak bound, applied to a random piece #

The habit worth keeping is the sampling step.

Euler’s formula gave a bound that charged one crossing per removed edge, which is hopelessly weak when edges carry many crossings. The fix was not a better inequality but a better place to apply the same one: a random sample of the points, thin enough that almost every surviving edge has few crossings left, where the weak bound is nearly sharp. Scaling back up, the crossings grow like the fourth power of the sampling rate and the edges like the square, and the gap between those exponents is the whole improvement.

That move — prove a weak statement about a random piece, then scale — is the probabilistic method at its most efficient, and it has the same shape as the argument by which a random colouring beats every explicit one in Ramsey theory. Averaging over pieces extracts from a coarse inequality the exponent it was hiding, and here the exponent turned a count of edges into a count of quadrilaterals.