Planar separator theorem

Every planar graph with n vertices has a set of O(√n) vertices whose removal divides it into components containing at most a fixed fraction of the vertices.

Baker's technique: A method for planar graphs that partitions vertices into layers and removes one layer to obtain bounded-treewidth subgraphs. Layering uses the same small-boundary principle to create tractable pieces.
Dynamic programming on tree decompositions: An algorithmic method that solves graph problems by combining solutions across bags of a tree decomposition. Separators help build decompositions that make exact computation feasible.
Richard J. Lipton: An American computer scientist known for contributions to computational complexity and algorithms. He co-authored the classical planar separator result.
Separator theorem: A result asserting that a graph family admits small vertex sets whose removal divides graphs into balanced components. The planar theorem is a particularly sharp instance of this broader kind of result.
Breadth-first search: A graph traversal that visits vertices in order of their shortest-path distance from a starting vertex. Distance layers provide the rings used in common separator proofs.
Planar graph isomorphism: The problem of deciding whether two planar graphs are isomorphic, meaning they have the same adjacency structure. Separator-based recursion supports efficient algorithms for comparing planar graphs.
Robert Endre Tarjan: An American computer scientist known for foundational work on graph algorithms and data structures. He co-authored the theorem's influential 1979 formulation.
Lipton–Tarjan separator theorem: A theorem giving a separator of at most 2√(2n) vertices that divides an n-vertex planar graph into components of size at most 2n/3. Its explicit constants distinguish the classical formulation from later variants.
Treewidth: A graph parameter measuring how closely a graph can be decomposed into overlapping tree-like regions. Small separators and tree decompositions express related forms of sparse graph structure.
Planar graph drawing: The representation of a planar graph in the plane with edges meeting only at shared endpoints. Separators can organize recursive layouts of large planar graphs.

Linked from 4 pages