Introduction

Imagine a country road map. Cities are dots, roads are lines, and — crucially — no two roads cross except at a city. Mathematicians call such a drawing a planar graph.

Now ask: can you find a small set of cities whose removal cuts the map into two roughly equal halves, with neither half containing too many cities? This is the separator problem, and the answer turns out to be remarkably clean.

In 1979, Richard Lipton and Robert Tarjan proved that every planar graph with nn vertices has a separator of size at most 22n2\sqrt{2n} — roughly O(n)O(\sqrt{n}) — such that both sides each contain at most 23n\tfrac{2}{3}n vertices. The theorem is proven and exact: the constant 222\sqrt{2} is achievable in linear time.

That n\sqrt{n} bound might look modest. But it is the difference between an algorithm that runs in O(n2)O(n^2) time and one that runs in O(nlog⁡n)O(n \log n) — a gap that, on a million-city map, shrinks hours of computation to seconds.

Try It: Divide a Map

The demo below shows a small planar graph drawn as a map. Click Find Separator to highlight the O(n)O(\sqrt{n}) separator vertices in red. Then click Split to color the two halves blue and green, and Recurse to keep dividing until every piece is small.

<p class="hint">A planar graph with <b id="n-label">16</b> vertices. Click <b>Find Separator</b>
    to discover the O(√n) separator (red). Then <b>Split</b> to color the two halves, and
    <b>Recurse</b> to keep dividing. Notice how few vertices the separator needs.</p>
<svg id="graph-svg" width="100%" viewBox="0 0 400 280"></svg>
<div class="status" id="status">Click "Find Separator" to begin.</div>
<div class="btns">
  <button id="btn-sep" type="button">Find Separator</button>
  <button id="btn-split" type="button" disabled>Split</button>
  <button id="btn-recurse" type="button" disabled>Recurse</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#graph-svg { display: block; border: 1px solid #d0d7de; border-radius: 10px;
             background: #f8fafc; max-height: 280px; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui,sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .38; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Planar Separator demo — divide-and-conquer on a planar map graph.
// The graph is a 4x4 grid (planar). We simulate the BFS-layer separator:
// find a middle BFS layer whose removal bisects the graph into two ≤2n/3 parts.

const W = 400, H = 280, R = 13;
// 4x4 grid: 16 nodes, edges only to horizontal/vertical neighbors (planar).
const COLS = 4, ROWS = 4;
const N = COLS * ROWS; // 16

function gridPos(i) {
  const col = i % COLS, row = Math.floor(i / COLS);
  const px = 55 + col * 100, py = 35 + row * 65;
  return { x: px, y: py };
}

// Build adjacency list for the 4x4 grid graph.
function buildGrid() {
  const adj = Array.from({ length: N }, () => []);
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      const i = r * COLS + c;
      if (c + 1 < COLS) { adj[i].push(i + 1); adj[i + 1].push(i); }
      if (r + 1 < ROWS) { adj[i].push(i + COLS); adj[i + COLS].push(i); }
    }
  }
  return adj;
}

// BFS from node 0, return layer assignment for each node.
function bfsLayers(adj, source, active) {
  const layer = new Array(N).fill(-1);
  if (!active.has(source)) return layer;
  const queue = [source];
  layer[source] = 0;
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    for (const v of adj[u]) {
      if (active.has(v) && layer[v] === -1) {
        layer[v] = layer[u] + 1;
        queue.push(v);
      }
    }
  }
  return layer;
}

// Find the BFS-layer separator for the active node set.
// Returns { separator: Set, sideA: Set, sideB: Set }.
function findSeparator(adj, active) {
  const n = active.size;
  const src = [...active][0];
  const layer = bfsLayers(adj, src, active);

  // Collect layers
  const maxL = Math.max(...[...active].map(v => layer[v]));
  const layers = [];
  for (let l = 0; l <= maxL; l++) {
    layers.push([...active].filter(v => layer[v] === l));
  }

  // Find middle layer where cumulative count crosses n/2
  let cum = 0, mid = 0;
  for (let l = 0; l <= maxL; l++) {
    cum += layers[l].length;
    if (cum >= n / 2) { mid = l; break; }
  }

  // Pick the smallest of mid-1, mid, mid+1 as separator
  const candidates = [mid - 1, mid, mid + 1].filter(l => l >= 0 && l <= maxL);
  const best = candidates.reduce((a, b) =>
    layers[a] && layers[b] && layers[a].length <= layers[b].length ? a : b, candidates[0]);

  const separator = new Set(layers[best] || []);

  // BFS to assign sides (excluding separator)
  const remaining = new Set([...active].filter(v => !separator.has(v)));
  const sideA = new Set(), sideB = new Set();
  // BFS from nodes below best layer
  const belowSrc = layers.slice(0, best).flat().filter(v => remaining.has(v));
  const aboveSrc = layers.slice(best + 1).flat().filter(v => remaining.has(v));

  function bfsFill(starts, target) {
    const q = [...starts];
    starts.forEach(v => target.add(v));
    let head = 0;
    while (head < q.length) {
      const u = q[head++];
      for (const w of adj[u]) {
        if (remaining.has(w) && !target.has(w) && !sideA.has(w) && !sideB.has(w)) {
          target.add(w); q.push(w);
        }
      }
    }
  }

  bfsFill(belowSrc, sideA);
  bfsFill([...remaining].filter(v => !sideA.has(v)), sideB);

  return { separator, sideA, sideB };
}

// ── State ──────────────────────────────────────────────────────────────────
const adj = buildGrid();
// colorMap: node -> 'none'|'sep'|'A'|'B'|'A2'|'B2'...
const colorMap = new Array(N).fill('none');
let currentSep = null, currentA = null, currentB = null;
let phase = 'idle'; // idle -> found -> split -> done

const svg = document.getElementById('graph-svg');
const statusEl = document.getElementById('status');
const btnSep = document.getElementById('btn-sep');
const btnSplit = document.getElementById('btn-split');
const btnRecurse = document.getElementById('btn-recurse');
const btnReset = document.getElementById('btn-reset');

const COLOR = {
  none: '#c9ccd1',
  sep: '#e63946',
  A: '#457b9d',
  B: '#2a9d8f',
  A2: '#1d3557',
  B2: '#264653',
};

function render() {
  svg.innerHTML = '';
  // Draw edges
  for (let u = 0; u < N; u++) {
    for (const v of adj[u]) {
      if (v > u) {
        const pu = gridPos(u), pv = gridPos(v);
        const line = document.createElementNS('http://www.w3.org/2000/svg', 'line');
        line.setAttribute('x1', pu.x); line.setAttribute('y1', pu.y);
        line.setAttribute('x2', pv.x); line.setAttribute('y2', pv.y);
        line.setAttribute('stroke', '#b0bec5'); line.setAttribute('stroke-width', '2');
        svg.appendChild(line);
      }
    }
  }
  // Draw nodes
  for (let i = 0; i < N; i++) {
    const p = gridPos(i);
    const c = document.createElementNS('http://www.w3.org/2000/svg', 'circle');
    c.setAttribute('cx', p.x); c.setAttribute('cy', p.y); c.setAttribute('r', R);
    c.setAttribute('fill', COLOR[colorMap[i]] || COLOR.none);
    c.setAttribute('stroke', '#fff'); c.setAttribute('stroke-width', '2');
    svg.appendChild(c);
    const t = document.createElementNS('http://www.w3.org/2000/svg', 'text');
    t.setAttribute('x', p.x); t.setAttribute('y', p.y + 5);
    t.setAttribute('text-anchor', 'middle');
    t.setAttribute('font-size', '11'); t.setAttribute('font-weight', 'bold');
    t.setAttribute('fill', colorMap[i] === 'none' ? '#333' : '#fff');
    t.textContent = i;
    svg.appendChild(t);
  }
}

function setStatus(msg, cls) {
  statusEl.textContent = msg;
  statusEl.className = 'status ' + (cls || '');
}

function resetState() {
  colorMap.fill('none');
  currentSep = null; currentA = null; currentB = null;
  phase = 'idle';
  btnSep.disabled = false; btnSplit.disabled = true; btnRecurse.disabled = true;
  setStatus('Click "Find Separator" to begin.');
  render();
}

btnSep.addEventListener('click', () => {
  const active = new Set(Array.from({ length: N }, (_, i) => i));
  const { separator, sideA, sideB } = findSeparator(adj, active);
  currentSep = separator; currentA = sideA; currentB = sideB;
  separator.forEach(v => colorMap[v] = 'sep');
  phase = 'found';
  btnSep.disabled = true; btnSplit.disabled = false; btnRecurse.disabled = true;
  setStatus(
    fmt('Separator: %size% vertices removed (≤ 2√(2·%N%) ≈ %v%). Left: %size2% | Right: %size3%.', { size: separator.size, N: N, v: (2 * Math.sqrt(2 * N)).toFixed(1), size2: sideA.size, size3: sideB.size }),
    'ok'
  );
  render();
});

btnSplit.addEventListener('click', () => {
  currentA.forEach(v => colorMap[v] = 'A');
  currentB.forEach(v => colorMap[v] = 'B');
  phase = 'split';
  btnSplit.disabled = true;
  btnRecurse.disabled = (currentA.size <= 1 && currentB.size <= 1);
  setStatus(
    fmt('Split: blue side (%size% nodes), green side (%size2% nodes). Now recurse!', { size: currentA.size, size2: currentB.size }),
    'info'
  );
  render();
});

btnRecurse.addEventListener('click', () => {
  // Split each side further using the same separator logic.
  let didWork = false;
  [['A', 'A2'], ['B', 'B2']].forEach(([parentColor, childColor]) => {
    const group = new Set([...Array(N).keys()].filter(i => colorMap[i] === parentColor));
    if (group.size <= 2) return; // already tiny
    const { separator, sideA, sideB } = findSeparator(adj, group);
    separator.forEach(v => colorMap[v] = 'sep');
    sideA.forEach(v => colorMap[v] = parentColor);
    sideB.forEach(v => colorMap[v] = childColor);
    didWork = true;
  });
  if (!didWork) {
    setStatus('All pieces are already small — recursion complete!', 'ok');
    btnRecurse.disabled = true;
  } else {
    const sepCount = colorMap.filter(c => c === 'sep').length;
    setStatus(fmt('Recursed: %sepCount% total separator vertices. Pieces are getting smaller.', { sepCount: sepCount }), 'ok');
  }
  render();
});

btnReset.addEventListener('click', resetState);

// Verify the core invariant: separator size ≤ ceil(2·sqrt(2·n))
(function verifySeparator() {
  const active = new Set(Array.from({ length: N }, (_, i) => i));
  const { separator, sideA, sideB } = findSeparator(adj, active);
  const bound = Math.ceil(2 * Math.sqrt(2 * N));
  console.assert(separator.size <= bound,
    'Separator size ' + separator.size + ' exceeds bound ' + bound);
  console.assert(sideA.size <= Math.ceil(2 * N / 3),
    'Side A too large: ' + sideA.size);
  console.assert(sideB.size <= Math.ceil(2 * N / 3),
    'Side B too large: ' + sideB.size);
  console.log(fmt('[planar-separator-demo] separator=%size% bound=%bound% A=%size2% B=%size3% — OK', { size: separator.size, bound: bound, size2: sideA.size, size3: sideB.size }));
})();

render();
Result
Console

Notice the asymmetry: the separator is tiny compared to the whole graph. Each split roughly halves the remaining nodes, so after O(log⁡n)O(\log n) rounds every piece fits in memory at once — that is the power of divide-and-conquer on planar graphs. Compare this with a general graph, where no such small separator is guaranteed and you might have to remove a linear fraction of nodes to balance the halves.

The Real Theorem

The key result, stated precisely:

Theorem (Lipton–Tarjan, 1979). Every planar graph GG with nn vertices has a vertex separator SS of size ∣S∣≤22n|S| \le 2\sqrt{2n} such that each connected component of G∖SG \setminus S contains at most 23n\tfrac{2}{3}n vertices.

The proof uses BFS layering:

  1. Root a BFS spanning tree and partition the vertices into layers L0,L1,…L_0, L_1, \ldots
  2. Find the middle layer LmL_m where the cumulative count crosses n/2n/2.
  3. By a counting argument (using Euler's formula V−E+F=2V - E + F = 2 for planar graphs), one of three consecutive layers Lm−1,Lm,Lm+1L_{m-1}, L_m, L_{m+1} has size at most 2n\sqrt{2n}.
  4. Deleting that middle band leaves the layers below and above as two roughly equal parts.

The theorem is proven and constructive — a linear-time algorithm computes the separator explicitly. No open problems remain about existence; the focus today is on finding the sparsest or best-balanced separator for specific graph families.

The result relates directly to graph coloring: planar graphs are 4-colorable (the Four Color Theorem), and separator-based divide-and-conquer gives an alternative path to many planarity results. It also underpins the fastest known algorithms for shortest paths on planar networks.

Where It Matters

The O(n)O(\sqrt{n}) separator is not just a curiosity — it is an engineering tool:

  • GPS and route planning: road networks are nearly planar. Preprocessing a road graph with recursive separator decomposition lets systems answer shortest-path queries in microseconds without exploring the full graph.
  • VLSI circuit layout: chip wiring diagrams are planar (or close to it). Separator-based partitioning assigns subcircuits to processing cores and reduces cross-chip communication.
  • Finite-element simulation: meshes for computational fluid dynamics and structural analysis are planar. Separators guide parallel solvers for large sparse linear systems.
  • Computational geometry: many divide-and-conquer algorithms for Voronoi diagrams and Delaunay triangulations exploit planar separability.
  • Approximation algorithms: for NP-hard problems on planar graphs (like independent set or vertex cover), separator-based dynamic programming yields polynomial-time approximation schemes (PTAS) — efficient approximate solutions that are otherwise out of reach.

The separator theorem is the reason that, even though graph problems can be NP-complete in general, the planar special case is often tractable.

Conclusion

The Planar Separator Theorem is one of those results that feels almost too good to be true: slice any planar graph in half by removing only O(n)O(\sqrt{n}) carefully chosen vertices. The theorem is proven — Lipton and Tarjan settled it in 1979 — and it can be computed in linear time.

The consequence is profound. Divide-and-conquer on planar graphs is cheap. Problems that seem intractable on general graphs become polynomial — sometimes even near-linear — when the input is planar. Road networks, chip layouts, geographic maps: they all hide this n\sqrt{n} gift.

So the next time your GPS recalculates a route in an instant, or a chip design tool places millions of transistors in seconds, remember: somewhere underneath is a tiny separator, quietly splitting the world in two.

Share this article

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

Comments

Loading comments...

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