In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of ⁠${\displaystyle O({\sqrt {n}})}$⁠ vertices from an n-vertex graph (where the O invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most ⁠${\displaystyle 2n/3}$⁠ vertices.

A weaker form of the separator theorem with ⁠${\displaystyle O({\sqrt {n}}\log ^{3/2}n)}$⁠ vertices in the separator instead of ⁠${\displaystyle O({\sqrt {n}})}$⁠ was originally proven by Ungar (1951), and the form with the tight asymptotic bound on the separator size was first proven by Lipton & Tarjan (1979). Since their work, the separator theorem has been reproven in several different ways, the constant in the ⁠${\displaystyle O({\sqrt {n}})}$⁠ term of the theorem has been improved, and it has been extended to certain classes of nonplanar graphs.

Repeated application of the separator theorem produces a separator hierarchy which may take the form of either a tree decomposition or a branch-decomposition of the graph. Separator hierarchies may be used to devise efficient divide and conquer algorithms for planar graphs, and dynamic programming on these hierarchies can be used to devise exponential time and fixed-parameter tractable algorithms for solving NP-hard optimization problems on these graphs. Separator hierarchies may also be used in nested dissection, an efficient variant of Gaussian elimination for solving sparse systems of linear equations arising from finite element methods.

Beyond planar graphs, separator theorems have been applied to other classes of graphs including graphs excluding a fixed minor, nearest neighbor graphs, and finite element meshes. The existence of a separator theorem for a class of graphs can be formalized and quantified by the concepts of treewidth and polynomial expansion.

As it is usually stated, the separator theorem states that, in any ${\displaystyle n}$-vertex planar graph ${\displaystyle G=(V,E)}$, there exists a partition of the vertices of ${\displaystyle G}$ into three sets ${\displaystyle A}$, ${\displaystyle S}$, and ${\displaystyle B}$, such that each of ${\displaystyle A}$ and ${\displaystyle B}$ has at most ${\displaystyle 2n/3}$ vertices, ${\displaystyle S}$ has ${\displaystyle O({\sqrt {n}})}$ vertices, and there are no edges with one endpoint in ${\displaystyle A}$ and one endpoint in ${\displaystyle B}$. It is not required that ${\displaystyle A}$ or ${\displaystyle B}$ form connected subgraphs of ${\displaystyle G}$. ${\displaystyle S}$ is called the separator for this partition.

An equivalent formulation is that the edges of any ${\displaystyle n}$-vertex planar graph ${\displaystyle G}$ may be subdivided into two edge-disjoint subgraphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ in such a way that both subgraphs have at least ${\displaystyle n/3}$ vertices and such that the intersection of the vertex sets of the two subgraphs has ${\displaystyle O({\sqrt {n}})}$ vertices in it. Such a partition is known as a separation. If a separation is given, then the intersection of the vertex sets forms a separator, and the vertices that belong to one subgraph but not the other form separated subsets each having at most ${\displaystyle 2n/3}$ vertices. In the other direction, if one is given a partition into three sets ${\displaystyle A}$, ${\displaystyle S}$, and ${\displaystyle B}$ that meet the conditions of the planar separator theorem, then one may form a separation in which the edges with an endpoint in ${\displaystyle A}$ belong to ${\displaystyle G_{1}}$, the edges with an endpoint in ${\displaystyle B}$ belong to ${\displaystyle G_{2}}$, and the remaining edges (with both endpoints in ${\displaystyle S}$) are partitioned arbitrarily.

The constant ${\displaystyle 2/3}$ in the statement of the separator theorem is arbitrary and may be replaced by any other number in the open interval ${\displaystyle (1/2,1)}$ without changing the form of the theorem: a partition into more equal subsets may be obtained from a less-even partition by repeatedly splitting the larger sets in the uneven partition and regrouping the resulting connected components.

Consider a grid graph with ${\displaystyle r}$ rows and ${\displaystyle c}$ columns; the number ${\displaystyle n}$ of vertices equals ${\displaystyle rc}$. For instance, in the illustration, ${\displaystyle r=5}$, ${\displaystyle c=8}$, and ${\displaystyle n=rc=40}$. If ${\displaystyle r}$ is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if ${\displaystyle c}$ is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing ${\displaystyle S}$ to be any of these central rows or columns, and removing ${\displaystyle S}$ from the graph, partitions the graph into two smaller connected subgraphs ${\displaystyle A}$ and ${\displaystyle B}$, each of which has at most ${\displaystyle n/2}$ vertices. If ${\displaystyle r\leq c}$ (as in the illustration), then choosing a central column will give a separator ${\displaystyle S}$ with ${\displaystyle r\leq {\sqrt {n}}}$ vertices, and similarly if ${\displaystyle c\leq r}$ then choosing a central row will give a separator with at most ${\displaystyle {\sqrt {n}}}$ vertices. Thus, every grid graph has a separator ${\displaystyle S}$ of size at most ${\displaystyle {\sqrt {n}}}$, the removal of which partitions it into two connected components, each of size at most ${\displaystyle n/2}$.