page_title: Planar separator theorem
section_title: Example
hierarchical_section_title: Planar separator theorem / Example
context_page_description: 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 O(√n) vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most 2n/3 vertices.
  A weaker form of the separator theorem with O(√n log n) vertices in the separator instead of O(√n) was originally proven by Ungar, and the form with the tight asymptotic bound on the separator size was first proven by Lipton & Tarjan. Since their work, the separator theorem has been reproven in several different ways, the constant in the O(√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.
context_section_description: Consider a grid graph with r rows and c columns; the number n of vertices equals rc. For instance, in the illustration, r = 5, c = 8, and n = 40. If r is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if c is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing S to be any of these central rows or columns, and removing S from the graph, partitions the graph into two smaller connected subgraphs A and B, each of which has at most n/2 vertices. If r ≤ c (as in the illustration), then choosing a central column will give a separator S with r ≤ √n vertices, and similarly if c ≤ r then choosing a central row will give a separator with at most √n vertices. Thus, every grid graph has a separator S of size at most √n, the removal of which partitions it into two connected components, each of size at most n/2.
  The planar separator theorem states that a similar partition can be constructed in any planar graph. The case of arbitrary planar graphs differs from the case of grid graphs in that the separator has size O(√n) but may be larger than √n, the bound on the size of the two subsets A and B (in the most common versions of the theorem) is 2n/3 rather than n/2, and the two subsets A and B need not themselves form connected subgraphs.
caption: A planar separator for a grid graph