Two graphs that will not lie flat

Four points, every pair joined by a line: the six lines can be drawn without a single crossing, and finding an arrangement that works takes about ten seconds with a pencil.

Five points, every pair joined: ten lines, and every arrangement anybody has ever tried has at least one crossing. That is a strong claim to make from failed attempts, and the reason it is true has nothing to do with attempts.

The search in that figure is honest about what it is. It tried six thousand random placements of the points for each graph, counted the crossings in every one, and kept the best. That establishes an upper bound on the crossing number and nothing else — a better arrangement might exist and the search might have missed it.

What rules out zero is a piece of arithmetic that never mentions a drawing.

Euler’s formula, turned into a ceiling #

A graph drawn in the plane without crossings cuts the plane into regions. Counting corners, edges and regions — including the unbounded region outside everything — always gives the same alternating sum:

$$V - E + F = 2.$$

Now count edges twice. Every face of the drawing is bounded by at least three edges, since two edges cannot enclose a region in a graph without repeated edges. And every edge borders exactly two faces. So counting edge-face incidences gives at least 3F on one side and exactly 2E on the other:

$$3F \le 2E.$$

Substituting F = 2 − V + E from Euler’s formula and rearranging gives

$$E \le 3V - 6.$$

That is a ceiling on how many edges a graph can have and still be drawable flat, and it is arithmetic on two numbers a graph carries about with it.

The two graphs that exceed it #

The complete graph on five points has 5 corners and 10 edges. The ceiling allows 3 × 5 − 6 = 9. Ten is more than nine, so no flat drawing exists — proved, from two counts, with no drawing attempted.

The second obstruction needs a refinement of the same argument. The graph joining three points to three other points — three houses to three utilities, in the version everybody meets as a puzzle — has 6 corners and 9 edges, and the ceiling of 3 × 6 − 6 = 12 does not rule it out.

But that graph has no triangles: every cycle in it alternates between the two sides and so has an even length of at least four. In a flat drawing of a triangle-free graph every face is bounded by at least four edges, so the count becomes 4F ≤ 2E, and the same substitution gives

$$E \le 2V - 4.$$

For the three-and-three graph that ceiling is 2 × 6 − 4 = 8, and it has 9 edges. One too many again.

Two graphs, two counting arguments differing by one number, and in both cases the impossibility is established by an inequality that a reader can check on a napkin.

The same ceiling, counted on the solids #

The inequality is worth seeing where it is tight, because that says which graphs are as dense as flatness permits.

Equality in 3F ≤ 2E happens exactly when every face is a triangle, so a graph achieving E = 3V − 6 is one whose flat drawing cuts the plane entirely into triangles. The tetrahedron, the octahedron and the icosahedron do it — 6 = 3 × 4 − 6, 12 = 3 × 6 − 6, 30 = 3 × 12 − 6 — and they are the reason the ceiling cannot be lowered.

That the list of regular solids stops at five is proved by a close relative of the same counting, and the two arguments sit either side of one identity. There, the counts are forced by requiring every face and every corner to look alike; here, they are bounded by requiring nothing at all. Both are Euler’s formula being asked a question about how much a flat structure can hold.

The remarkable part: those are the only two #

Ruling out two graphs is a small result. What makes planarity a subject is Kuratowski’s theorem, and it is one of the most satisfying classification statements in mathematics.

A graph can be drawn in the plane without crossings if and only if it contains neither of those two graphs, in the sense of containing a subdivision of one.

A subdivision means the edges may have extra points sitting along them — a path of three edges counts as an edge that has been stretched. With that allowance, every non-planar graph in existence, however large and however complicated, has one of exactly two obstructions hiding inside it.

That is a strong statement about an infinite family, and its form is worth noticing: an infinite class characterised by a finite list of forbidden pieces. Such characterisations are rare and valuable, and the general theory of when they exist — the graph minor theorem — took two decades and hundreds of pages, with this as its first and simplest instance.

The shape of the statement deserves a moment on its own, because it is doing something an inequality cannot. The edge-count ceiling is a necessary condition: exceed it and the graph is certainly not planar. It is not sufficient, and the gap is easy to exhibit — take the two forbidden graphs and hang a long path off each, and the edge count falls well under the ceiling while the obstruction is still inside. Kuratowski’s theorem closes exactly that gap, replacing a test that can only ever say no with one that decides. Necessary conditions are cheap and common; conditions that are both necessary and sufficient are what a subject is trying to reach, and they usually arrive much later than the first bound does.

What it decides elsewhere #

Planarity is not a curiosity about drawings; it is a hypothesis that other theorems need.

The four-colour theorem is a theorem about planar graphs and about nothing else. Five points every pair joined would need five colours, and the theorem is not contradicted because that graph is not planar. Every map on a flat sheet becomes a graph by putting a corner in each region and joining regions that share a border, and the drawing of that graph has no crossings for the geometric reason that two borders cannot cross.

The same edge-counting argument gives the four-colour theorem’s easy relative. From E ≤ 3V − 6 it follows that the average degree of a planar graph is below six, so some corner has degree at most five — and that observation, applied repeatedly, proves that six colours always suffice in a page of work. Getting from six to five takes a clever argument, and getting from five to four took a computer.

Planarity also decides which circuits can be printed on one layer of a board, which is where the question is asked most often outside mathematics, and whether a graph’s dual makes sense — a construction that needs a drawing to be defined at all.

It is worth noticing which graphs on this site are planar and which are not, since the property is easy to check and rarely mentioned. The graph behind the party of six is the complete graph on six points, which contains the five-point one and is therefore about as far from planar as a small graph gets — the Ramsey argument is completely indifferent to that, because it never draws anything. The graph joining each point to its nearest neighbours in a plane divided by proximity is planar by construction, since its edges are built from a drawing rather than being fitted to one afterwards. The distinction between a graph that happens to be planar and one that arrives with a drawing attached is worth keeping, and the second kind is where the fast algorithms are used.

Give it a handle and both fit #

Nothing in the argument was about the plane as such. It used Euler’s formula, and Euler’s formula depends on the surface being drawn on.

On a surface where the alternating sum is χ rather than 2, the same double count gives E ≤ 3V − 3χ. For a torus, χ is 0 and the ceiling becomes 3V, which allows the complete graph on five points with room to spare — and indeed both forbidden graphs can be drawn on a torus without crossings, by routing one edge round through the hole.

The genus of a graph is the smallest number of handles a surface needs before the graph fits. It is 0 for planar graphs, 1 for the two obstructions here, and grows for larger complete graphs; every surface has its own finite list of forbidden pieces, though the lists are known explicitly only for the plane and the projective plane, where there are 35 of them.

The colour count moves too. The seven-colour bound on a torus follows from the shifted ceiling by the same averaging argument that gives six on the plane, and unlike the plane’s case it is achieved: there is a map on a torus needing all seven, and it can be drawn.

The number of crossings, when there must be some #

If a graph cannot be drawn flat, the natural follow-up is how few crossings are unavoidable. That number is the crossing number, and it is a much harder quantity than planarity.

For the five-point complete graph it is 1, and both halves of that claim are visible above: the search found a drawing with one crossing, and the edge count rules out zero. For the complete graph on six points it is 3, on seven it is 9, and by ten points the value was an open problem for decades.

The general question is hard in the strongest sense — deciding whether a graph’s crossing number is below a given value is NP-complete — and even for complete graphs there is only a conjectured formula, verified up to twelve points and unproven beyond.

There is also a subtlety the figures here quietly rely on. Drawing edges as straight segments can force more crossings than drawing them as curves; the rectilinear crossing number is a different and generally larger quantity. For the two graphs above the two numbers agree at 1, so the pictures are honest, but for larger complete graphs they diverge, and a search over straight-line layouts stops being evidence about the crossing number at all.

A bound on crossings, from the same inequality #

The crossing number is hard to compute exactly and easy to bound from below, and the bound comes from the ceiling above by a manoeuvre worth seeing, because the result it leads to is in a different subject entirely.

Start with the crudest observation. If a graph is drawn with $c$ crossings, deleting one edge at each crossing leaves a planar graph, so $E - c \le 3V - 6$, giving $c \ge E - 3V$. That is true and weak: it says nothing at all once the edge count is under three times the vertex count.

Now amplify it by sampling. Keep each vertex independently with probability $p$, and keep an edge when both its ends survive. On average the surviving graph has $pV$ vertices, $p^2E$ edges and $p^4c$ crossings, since a crossing needs all four of its endpoints. Applying the crude bound to the surviving graph and taking averages,

$$p^4 c \ \ge\ p^2 E - 3pV.$$

Divide by $p^4$ and choose $p$ to make the right side as large as possible — $p = 4V/E$ works — and the result is the crossing number inequality:

$$c \ \ge\ \frac{E^3}{64\,V^2}$$

whenever $E$ is at least four times $V$. A graph that is even moderately dense must have crossings not merely in the dozens but cubically many in its edge count.

The application is what makes it famous, and it is not about graphs. Take $n$ points and $m$ lines in the plane and ask how many times a point can lie on a line. Build a graph: the points are the vertices, and two points are joined when they are consecutive along one of the lines. Then the number of incidences is at most the number of edges plus $m$, and the graph is drawn in the plane with crossings only where two lines cross — at most $m^2$ of them. Feeding those two facts into the inequality and rearranging gives

$$\text{incidences} = O\!\left((nm)^{2/3} + n + m\right),$$

which is the Szemerédi–Trotter theorem, and it is sharp. Székely’s proof, in 1997, is the three lines above; the original proof of 1983 was long and technical.

That is as clean an example as this collection has of a bound migrating between subjects. Euler’s formula gave a ceiling on edges; the ceiling gave a floor on crossings; sampling amplified the floor; and the amplified floor settled a question about points and lines that has nothing to do with drawing graphs at all. Each step is elementary and none of them is about the subject the answer lands in, which is the usual sign that the quantity being tracked — here, how much structure a flat surface can hold — was the right one all along.

What it costs #

Deciding planarity is fast. There are algorithms that answer in time proportional to the number of edges — remarkably, no worse than reading the graph in — by attempting to build a drawing and failing in a way that exhibits an obstruction. The first such algorithm dates from 1974 and the subject has produced several since, each simpler than the last.

Finding a Kuratowski obstruction inside a non-planar graph is also linear, so the negative answer comes with a certificate: a subgraph a reader can check by hand. That is unusually good behaviour for a decision problem, and it is why planarity testing is a standard library routine rather than a research topic.

The counting bound costs nothing at all and answers the question in the direction that matters most often. If a graph has more than 3V − 6 edges it is not planar, full stop, and that test is two integers and a comparison. It gives no information in the other direction — plenty of non-planar graphs have few edges — but as a first filter it is free.

What the picture cannot show #

The drawings above are three graphs in three particular layouts, and the theorem is about every layout of every graph. The search behind them can only ever report the best thing it found; the impossibility comes from the inequality, and an inequality has no picture.

Nor can a figure show a subdivision hiding inside a large graph. Kuratowski’s theorem is about containment, and finding the contained copy in a graph with a thousand edges is an algorithmic matter with no visual character.

And the pictures are all of straight-line drawings, which is a restriction the theory does not make. That every planar graph can in fact be drawn with straight edges is a separate theorem — Fáry’s — and it is what licenses these figures to be evidence about planarity at all.

The ladder from here #

Rungs above: Kuratowski’s theorem proved, and the equivalent statement in terms of minors rather than subdivisions. Fáry’s theorem, that a planar graph can always be drawn with straight edges. The dual graph, and how the four-colour theorem becomes a statement about colouring faces. Graphs on surfaces other than the plane: the torus accepts both forbidden graphs, and every surface has its own finite list of obstructions. The genus of a graph, and the seven colours a map on a torus can need. Planar separator theorems, which say a planar graph can be cut into halves by removing very few corners, and are what makes planar algorithms fast. And the graph minor theorem, which says every family closed under minors has a finite list of obstructions — the most general form of what Kuratowski found first.

The shape of the idea #

The argument at the centre of this essay is a double count wearing a topologist’s hat, and it is worth extracting from the graph theory.

Something is counted in two ways — edge-face incidences, once from the faces and once from the edges — and the two counts are compared. One of them is an inequality because a face needs at least three edges; the other is an equality because an edge borders exactly two faces. Feeding both into a formula that was proved elsewhere converts a topological fact into an arithmetical ceiling.

Every step is elementary and the conclusion is not: a statement about all possible drawings, which are infinite in number and impossible to enumerate, reduced to a comparison of two whole numbers. Counting the same thing twice is the oldest trick in the subject and it keeps producing results that no amount of drawing would ever settle.