Planar Separator Theorem

The planar separator theorem, in graph theory, is a form of isoperimetric inequality for planar graphs stating that any planar graph on n vertices can be split into smaller pieces by removing a small number of vertices. Removing O(square root of n) vertices can partition the graph into disjoint pieces each with at most two thirds of the vertices; a weaker bound was proved by Ungar in 1951, and Lipton and Tarjan proved the tight bound in 1979, a result since used to build separator hierarchies for divide-and-conquer algorithms, dynamic programming on NP-hard problems, and nested dissection methods for sparse linear systems. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/