Non-Planar Graph Generator

What this generator does

Starts from K5 or K3,3, lets some of its joins run through an extra corner instead of being a single edge, hangs a few unrelated corners off the result, and then renumbers everything so the pattern is not simply the first few corners. What comes back is the graph, and the certificate: which corners are the pattern’s, and which path realises each of its joins.

How to use this tool

1. Choose which pattern to hide, how many of its joins run through an extra corner, and how many corners have nothing to do with it.
2. Try to redraw the graph without a crossing. You cannot, and that is the point.
3. Reveal the proof, and follow each path along the edge list to confirm it is really there.
4. Copy the link to hand somebody the same graph.

Understanding the controls

Pattern

K5 is five corners with every pair joined; K3,3 is three and three with every one of the first joined to every one of the second. Between them they are the only two obstructions there are.

Joins split by a corner

How many of the pattern’s joins run through an extra corner rather than being a single edge. Splitting a join keeps the obstruction and makes it harder to see.

Extra corners

Corners hung off the graph that play no part in the proof. They make the certificate worth having rather than obvious.

Repeat word

The word this graph was built from. Anyone opening the same link gets the same graph and the same proof.

Common use cases

• Teaching planarity with an example whose answer is not a matter of trying harder
• A worked exercise in Kuratowski’s theorem, with the subdivision already found
• Test material for a planarity-checking algorithm, where the expected answer is known
• Showing why the edge-count test is one-way: many of these are far under the limit
• Setting the same problem for a whole class from one link

How this generator works

The certificate is walked against the finished edge list rather than taken from the recipe. Each path is stepped along and every step confirmed to be an edge that is really there; each path is confirmed to start and end at the corners it claims; the paths are confirmed to share nothing but their ends, which is what makes them a subdivision rather than a tangle; and there is confirmed to be exactly one path for each join the pattern requires, with none left over. Where the graph is dense enough there is a second and quite separate test — a flat drawing on n corners can hold at most 3n − 6 edges — and the page says when that applies and when it settles nothing.

Randomness and fairness

The graph is built from a repeat word taken from your browser’s secure generator unless you type one of your own, so the same link gives the same problem to everybody. A repeat word makes a graph reproducible and is not a security measure; nothing here is suitable for anything that has to stay secret.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

• The graph is built around an obstruction rather than drawn at random and tested, so these are examples of non-planarity rather than a fair sample of graphs.
• The certificate is one subdivision, not every one. A graph may hide several, and finding a different one is not a disagreement.
• The edge-count test only ever points one way. A graph under the limit may still be non-planar, and most of the ones here are under it.
• The picture puts the corners on a circle. It is not an attempt at a good drawing, because no good drawing exists.
• Only the two obstructions of Kuratowski’s theorem are here. Minors, Wagner’s form of the theorem and the wider theory of forbidden minors are all outside this.

Privacy and your data

The graph and the proof are worked out in your browser, and nothing about them is sent anywhere or kept. The repeat word is a short label this page minted or you typed, and it is the only part that appears in the address.