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 vertices from an -vertex graph (where the invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most vertices.
A weaker form of the separator theorem with vertices in the separator instead of was originally proven by , and the form with the tight asymptotic bound on the separator size was first proven by . Since their work, the separator theorem has been reproven in several different ways, the constant in the 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.
Statement of the theorem As it is usually stated, the separator theorem states that, in any -vertex planar graph , there exists a partition of the vertices of into three sets , , and , such that each of and has at most vertices, has vertices, and there are no edges with one endpoint in and one endpoint in . It is not required that or form connected subgraphs of . is called the separator for this partition.
An equivalent formulation is that the edges of any -vertex planar graph may be subdivided into two edge-disjoint subgraphs and in such a way that both subgraphs have at least vertices and such that the intersection of the vertex sets of the two subgraphs has 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 vertices. In the other direction, if one is given a partition into three sets , , and that meet the conditions of the planar separator theorem, then one may form a separation in which the edges with an endpoint in belong to , the edges with an endpoint in belong to , and the remaining edges (with both endpoints in ) are partitioned arbitrarily.
The constant in the statement of the separator theorem is arbitrary and may be replaced by any other number in the open interval 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.
Example
Consider a grid graph with rows and columns; the number of vertices equals . For instance, in the illustration, , , and . If is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing to be any of these central rows or columns, and removing from the graph, partitions the graph into two smaller connected subgraphs and , each of which has at most vertices. If (as in the illustration), then choosing a central column will give a separator with vertices, and similarly if then choosing a central row will give a separator with at most vertices. Thus, every grid graph has a separator of size at most , the removal of which partitions it into two connected components, each of size at most .. Instead of using a row or column of a grid graph, George partitions the graph into four pieces by using the union of a row and a column as a separator.
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 but may be larger than , the bound on the size of the two subsets and (in the most common versions of the theorem) is rather than , and the two subsets and need not themselves form connected subgraphs.
Constructions
Breadth-first layering augment the given planar graph by additional edges, if necessary, so that it becomes maximal planar (every face in a planar embedding is a triangle). They then perform a breadth-first search, rooted at an arbitrary vertex , and partition the vertices into levels by their distance from . If is the median level (the level such that the numbers of vertices at higher and lower levels are both at most ) then there must be levels and that are steps above and below respectively and that contain vertices, respectively, for otherwise there would be more than vertices in the levels near . They show that there must be a separator formed by the union of and , the endpoints of an edge of that does not belong to the breadth-first search tree and that lies between the two levels, and the vertices on the two breadth-first search tree paths from the endpoints of back up to level . The size of the separator constructed in this way is at most . The vertices of the separator and the two disjoint subgraphs can be found in linear time.
This proof of the separator theorem applies as well to weighted planar graphs, in which each vertex has a non-negative cost. The graph may be partitioned into three sets , , and such that and each have at most of the total cost and has vertices, with no edges from and . By analysing a similar separator construction more carefully, shows that the bound on the size of can be reduced to .
suggest a simplified version of this approach: they augment the graph to be maximal planar and construct a breadth first search tree as before. Then, for each edge that is not part of the tree, they form a cycle by combining with the tree path that connects its endpoints. They then use as a separator the vertices of one of these cycles. Although this approach cannot be guaranteed to find a small separator for planar graphs of high diameter, their experiments indicate that it outperforms the Lipton–Tarjan and Djidjev breadth-first layering methods on many types of planar graph.
Simple cycle separators For a graph that is already maximal planar it is possible to show a stronger construction of a simple cycle separator, a cycle of small length such that the inside and the outside of the cycle (in the unique planar embedding of the graph) each have at most vertices. proves this (with a separator size of ) by using the Lipton–Tarjan technique for a modified version of breadth first search in which the levels of the search form simple cycles.
prove the existence of simple cycle separators more directly: let be a cycle of at most vertices, with at most vertices outside , that forms as even a partition of inside and outside as possible. They show that these assumptions force to be a separator. For otherwise, the distances within must equal the distances in the disk enclosed by (a shorter path through the interior of the disk would form part of the boundary of a better cycle). Additionally, must have length exactly , as otherwise it could be improved by replacing one of its edges by the other two sides of a triangle. If the vertices in are numbered (in clockwise order) from to , and vertex is matched up with vertex , then these matched pairs can be connected by vertex-disjoint paths within the disk, by a form of Menger's theorem for planar graphs. However, the total length of these paths would necessarily exceed , a contradiction. With some additional work they show by a similar method that there exists a simple cycle separator of size at most .
further improved the constant factor in the simple cycle separator theorem to . Their method can also find simple cycle separators for graphs with non-negative vertex weights, with separator size at most , and can generate separators with smaller size at the expense of a more uneven partition of the graph. In biconnected planar graphs that are not maximal, there exist simple cycle separators with size proportional to the Euclidean norm of the vector of face lengths that can be found in near-linear time.
Circle separators According to the Koebe–Andreev–Thurston circle-packing theorem, any planar graph may be represented by a packing of circular disks in the plane with disjoint interiors, such that two vertices in the graph are adjacent if and only if the corresponding pair of disks are mutually tangent. As show, for such a packing, there exists a circle that has at most disks touching or inside it, at most disks touching or outside it, and that crosses disks.
To prove this, Miller et al. use stereographic projection to map the packing onto the surface of a unit sphere in three dimensions. By choosing the projection carefully, the center of the sphere can be made into a centerpoint of the disk centers on its surface, so that any plane through the center of the sphere partitions it into two halfspaces that each contain or cross at most of the disks. If a plane through the center is chosen uniformly at random, a disk will be crossed with probability proportional to its radius. Therefore, the expected number of disks that are crossed is proportional to the sum of the radii of the disks. However, the sum of the squares of the radii is proportional to the total area of the disks, which is at most the total surface area of the unit sphere, a constant. An argument involving Jensen's inequality shows that, when the sum of squares of non-negative real numbers is bounded by a constant, the sum of the numbers themselves is . Therefore, the expected number of disks crossed by a random plane is and there exists a plane that crosses at most that many disks. This plane intersects the sphere in a great circle, which projects back down to a circle in the plane with the desired properties. The disks crossed by this circle correspond to the vertices of a planar graph separator that separates the vertices whose disks are inside the circle from the vertices whose disks are outside the circle, with at most vertices in each of these two subsets.;
This method leads to a randomized algorithm that finds such a separator in linear time, and a less-practical deterministic algorithm with the same linear time bound. By analyzing this algorithm carefully using known bounds on the packing density of circle packings, it can be shown to find separators of size at most
Although this improved separator size bound comes at the expense of a more-uneven partition of the graph, argue that it provides an improved constant factor in the time bounds for nested dissection compared to the separators of . The size of the separators it produces can be further improved, in practice, by using a nonuniform distribution for the random cutting planes.
The stereographic projection in the Miller et al. argument can be avoided by considering the smallest circle containing a constant fraction of the centers of the disks and then expanding it by a constant picked uniformly in the range . As in Miller et al., the disks intersecting the expanded circle form a valid separator, and in expectation, the separator is of the right size. The resulting constants are somewhat worse.
Spectral partitioning