Planarity Testing

Here is an old puzzle. Draw three houses and three wells. Connect every house to every well with a path — and never let two paths cross. Try it on paper and you will fail, every time. Something stops you.

That "something" has a name: the graph of three houses and three wells, written $K_{3}$,₃, simply cannot be drawn in the plane without a crossing. A graph that can be drawn flat with no crossing edges is called planar.

So a natural question appears: given any tangle of dots and lines, can it be redrawn flat, with no edges crossing? It sounds geometric — like it should require cleverly sliding points around until the knots come undone. You might expect it to be slow, even hopeless, for big graphs.

It is the opposite. Deciding planarity is one of the great easy problems of computer science.

Below is a graph with its vertices scattered around. Some edges cross. Drag the dots and try to arrange them so that no two edges cross — that proves the graph is planar.

<p class="hint">{{hint}}</p>
<div class="picker">
  <button data-g="cycle" class="on" type="button">{{btn_cycle}}</button>
  <button data-g="cube" type="button">{{btn_cube}}</button>
  <button data-g="k5" type="button">K&#8325;</button>
  <button data-g="k33" type="button">K&#8323;&#8323;</button>
</div>
<svg id="canvas" viewBox="0 0 320 240" aria-label="{{canvas_aria}}"></svg>
<div class="status" id="status">{{status_drag}}</div>
<div class="btns">
  <button id="test" type="button">{{btn_test}}</button>
  <button id="shuffle" type="button" class="ghost">{{btn_shuffle}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.picker { display: flex; gap: .4rem; flex-wrap: wrap; margin: 0 0 .5rem; }
.picker button { font: 600 13px system-ui, sans-serif; padding: .35rem .7rem; border: 1px solid #cdd9e3;
                 background: #e8eef3; color: #1d3557; border-radius: 7px; cursor: pointer; }
.picker button.on { background: #1d3557; color: #fff; border-color: #1d3557; }
#canvas { width: 100%; max-width: 320px; height: 240px; background: #f5f8fa; border: 1px solid #cdd9e3;
          border-radius: 10px; touch-action: none; display: block; }
.edge { stroke: #8aa0b4; stroke-width: 2; }
.edge.cross { stroke: #e63946; stroke-width: 2.6; }
.node { fill: #1d3557; stroke: #fff; stroke-width: 2; cursor: grab; }
.node:active { cursor: grabbing; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
.btns button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.btns button.ghost { background: #fff; color: #1d3557; }

// Code not found

Switch between the examples. The cycle and the cube can always be untangled if you place the points well. But $K_{5}$ (five dots, all connected) and $K_{3}$,₃ (the three-houses puzzle) can never be drawn flat, no matter how you drag — they are the two forbidden shapes at the heart of the theory. The Test planarity button runs the real decision in an instant: it never needs to guess your dragging, it just answers yes or no.

How hard is planarity, really? Easy — provably easy.

• It's solved. In 1974 John Hopcroft and Robert Tarjan gave an algorithm that decides planarity in linear time — $O(V)$, proportional to the size of the graph. You cannot do meaningfully better, because you must at least read the input.
• The obstructions are finite and known. Back in 1930 Kazimierz Kuratowski proved a stunning fact: a graph is non-planar if and only if it secretly contains one of just two shapes — $K_{5}$ (five mutually connected points) or $K_{3}$,₃ (the three-houses graph). Every tangle that can't lie flat hides one of these two, and nothing else.
• Euler's formula gives a quick sanity check. For any planar drawing, V − E + F = 2, which forces E ≤ 3V − 6. A simple graph with more edges than that is instantly non-planar — no algorithm needed.

That is the surprise. A problem dressed up as geometry — "slide the points until the knots fall out" — turns out to be combinatorial and linear. It sits comfortably inside P, the class of efficiently solvable problems, with no exponential blow-up hiding anywhere. Contrast that with its lookalikes: deciding whether a graph can be drawn with at most k crossings is NP-hard, and so is graph coloring. Planarity is the lucky one.

"Can this network be laid out flat without crossings?" turns out to be a very practical question:

• Circuit and chip layout: a planar circuit can be printed on a single layer with no wires jumping over each other. Testing planarity tells designers when they need a second layer.
• Graph drawing and visualization: tools that lay out diagrams, metro maps and flowcharts use planarity tests to find the cleanest, crossing-free arrangement when one exists.
• The four color theorem: every planar map can be colored with four colors so no neighbors clash — a famous result that only makes sense because planarity is a sharp, decidable property. See graph coloring.
• Algorithm speedups: many problems that are hard in general become much easier on planar graphs, so testing planarity first can unlock a faster path.

Because the test is linear, it can run as a quiet first step in much larger pipelines without ever becoming the bottleneck.

Planarity testing is a lesson in not judging a problem by its costume. It looks like fiddly geometry — endless sliding of points — yet the truth underneath is crisp: there are exactly two obstructions, $K_{5}$ and $K_{3}$,₃, and a linear-time algorithm settles the question for any graph at all.

So the next time you stare at a tangle of wires or a knotted diagram wondering whether it can ever be drawn cleanly, remember: a computer can tell you in a single sweep. Not every hard-looking problem is hard — and the line between P and NP runs right between planarity and its crossing-counting cousins.