Introduction

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 K3K_{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.

Try It: Untangle the Graph

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">Drag the dots to remove every edge crossing. A graph is <b>planar</b> if it can be drawn flat with no crossings. Some graphs (K&#8325; and K&#8323;&#8323;) can <b>never</b> be untangled — press <b>Test planarity</b> to find out instantly.</p>
<div class="picker">
  <button data-g="cycle" class="on" type="button">Cycle</button>
  <button data-g="cube" type="button">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="graph"></svg>
<div class="status" id="status">Drag the dots to untangle.</div>
<div class="btns">
  <button id="test" type="button">Test planarity</button>
  <button id="shuffle" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Planarity testing demo. The user drags vertices to remove crossings.
// Crossings are detected with a segment-intersection test (live, while dragging).
// "Test planarity" answers the real question: is the graph planar AT ALL?
// For these small named graphs the answer is known from Kuratowski's theorem:
// a graph is non-planar iff it contains K5 or K3,3. Here the planar examples
// (cycle, cube) are planar; k5 and k33 are exactly the two forbidden graphs.
const svg = document.getElementById('canvas');
const NS = 'http://www.w3.org/2000/svg';
const W = 320, H = 240;

// Each graph: list of edges [a,b]; planar flag (the true answer).
const GRAPHS = {
  cycle: { n: 6, edges: [[0,1],[1,2],[2,3],[3,4],[4,5],[5,0]], planar: true },
  cube:  { n: 8, edges: [[0,1],[1,2],[2,3],[3,0],[4,5],[5,6],[6,7],[7,4],
                         [0,4],[1,5],[2,6],[3,7]], planar: true },
  k5:    { n: 5, edges: [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]], planar: false },
  k33:   { n: 6, edges: [[0,3],[0,4],[0,5],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]], planar: false }
};
let key = 'cycle';
let pts = [];        // {x,y} per node
let drag = null;

function randomLayout(n){
  const p = [];
  for(let i=0;i<n;i++) p.push({ x: 40 + Math.random()*(W-80), y: 30 + Math.random()*(H-60) });
  return p;
}
function load(k){
  key = k; pts = randomLayout(GRAPHS[k].n);
  document.querySelectorAll('.picker button').forEach(b=>b.classList.toggle('on', b.dataset.g===k));
  setStatus('Drag the dots to untangle.','');
  render();
}

// Do segments AB and CD properly cross (excluding shared endpoints)?
function orient(a,b,c){ return Math.sign((b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x)); }
function segCross(a,b,c,d){
  const o1=orient(a,b,c), o2=orient(a,b,d), o3=orient(c,d,a), o4=orient(c,d,b);
  return o1!==o2 && o3!==o4 && o1!==0 && o2!==0 && o3!==0 && o4!==0;
}
// Count crossings in the CURRENT drawing (only non-adjacent edge pairs).
function countCrossings(){
  const E = GRAPHS[key].edges; const set = new Set(); let total = 0;
  for(let i=0;i<E.length;i++) for(let j=i+1;j<E.length;j++){
    const [a,b]=E[i], [c,d]=E[j];
    if(a===c||a===d||b===c||b===d) continue; // share a vertex: never count
    if(segCross(pts[a],pts[b],pts[c],pts[d])){ total++; set.add(i); set.add(j); }
  }
  return { total, set };
}

function render(){
  const { set } = countCrossings();
  svg.innerHTML = '';
  const E = GRAPHS[key].edges;
  E.forEach(([a,b],i)=>{
    const ln = document.createElementNS(NS,'line');
    ln.setAttribute('x1',pts[a].x); ln.setAttribute('y1',pts[a].y);
    ln.setAttribute('x2',pts[b].x); ln.setAttribute('y2',pts[b].y);
    ln.setAttribute('class','edge'+(set.has(i)?' cross':''));
    svg.appendChild(ln);
  });
  pts.forEach((p,i)=>{
    const c = document.createElementNS(NS,'circle');
    c.setAttribute('cx',p.x); c.setAttribute('cy',p.y); c.setAttribute('r',9);
    c.setAttribute('class','node'); c.dataset.i = i;
    svg.appendChild(c);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function toLocal(ev){
  const r = svg.getBoundingClientRect();
  const t = ev.touches ? ev.touches[0] : ev;
  return { x:(t.clientX-r.left)/r.width*W, y:(t.clientY-r.top)/r.height*H };
}
function start(ev){ const t=ev.target; if(t.classList.contains('node')){ drag=+t.dataset.i; ev.preventDefault(); } }
function move(ev){
  if(drag===null) return; const p=toLocal(ev);
  pts[drag].x=Math.max(12,Math.min(W-12,p.x)); pts[drag].y=Math.max(12,Math.min(H-12,p.y));
  render(); ev.preventDefault();
  const c=countCrossings().total;
  if(c===0) setStatus('No crossings in this drawing!','ok');
  else setStatus(fmt('%c% crossing%v% left.', { c: c, v: c>1?'s':'' }),'');
}
function end(){ drag=null; }

svg.addEventListener('mousedown',start); window.addEventListener('mousemove',move); window.addEventListener('mouseup',end);
svg.addEventListener('touchstart',start,{passive:false}); window.addEventListener('touchmove',move,{passive:false}); window.addEventListener('touchend',end);

document.querySelectorAll('.picker button').forEach(b=>b.addEventListener('click',()=>load(b.dataset.g)));
document.getElementById('shuffle').addEventListener('click',()=>{ pts=randomLayout(GRAPHS[key].n); render(); setStatus('Drag the dots to untangle.',''); });
document.getElementById('test').addEventListener('click',()=>{
  const planar = GRAPHS[key].planar;
  if(planar){
    const c = countCrossings().total;
    if(c===0) setStatus('Planar — and your drawing already has no crossings!','ok');
    else setStatus('Planar: a crossing-free drawing exists. Keep dragging to find it.','ok');
  } else {
    setStatus(fmt('Non-planar: this graph contains %v% — no drawing is ever crossing-free.', { v: key==='k5'?'K₅':'K₃₃' }),'bad');
  }
  console.log('graph',key,'planar?',planar,'| current crossings',countCrossings().total);
});
load('cycle');
Result
Console

Switch between the examples. The cycle and the cube can always be untangled if you place the points well. But K5K_{5} (five dots, all connected) and K3K_{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.

The Real Complexity

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)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 — K5K_{5} (five mutually connected points) or K3K_{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.

Where It Matters

"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.

Conclusion

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, K5K_{5} and K3K_{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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/planarity-testing/Content licensed under CC BY-NC 4.0.