Planar separator theorem
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 formula_1 vertices from an formula_2-vertex graph (where the formula_3 invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most formula_4 vertices. A weaker form of the separator theorem with formula_5 vertices in the separator instead of formula_1 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 formula_7 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 formula_2-vertex planar graph formula_9, there exists a partition of the vertices of formula_10 into three sets formula_11, formula_12, and formula_13, such that each of formula_11 and formula_13 has at most formula_4 vertices, formula_12 has formula_7 vertices, and there are no edges with one endpoint in formula_11 and one endpoint in formula_13. It is not required that formula_11 or formula_13 form connected subgraphs of formula_10. formula_12 is called the separator for this partition. An equivalent formulation is that the edges of any formula_2-vertex planar graph formula_10 may be subdivided into two edge-disjoint subgraphs  formula_27 and formula_28 in such a way that both subgraphs have at least formula_29 vertices and such that the intersection of the vertex sets of the two subgraphs has formula_7 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 formula_4 vertices. In the other direction, if one is given a partition into three sets formula_11, formula_12, and formula_13 that meet the conditions of the  planar separator theorem, then one may form a separation in which the edges with an endpoint in formula_11 belong to formula_27, the edges with an endpoint in formula_13 belong to formula_28, and the remaining edges (with both endpoints in formula_12) are partitioned arbitrarily. The constant formula_40 in the statement of the separator theorem is arbitrary and may be replaced by any other number in the open interval formula_41 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 formula_42 rows and formula_43 columns; the number formula_2 of vertices equals formula_45. For instance, in the illustration, formula_46, formula_47, and formula_48. If formula_42 is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if formula_43 is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing formula_12 to be any of these central rows or columns, and removing formula_12 from the graph, partitions the graph into two smaller connected subgraphs  formula_11 and formula_13, each of which has at most formula_55 vertices. If formula_56 (as in the illustration), then choosing a central column will give a separator formula_12 with formula_58 vertices, and similarly if formula_59 then choosing a central row will give a separator with at most formula_60 vertices. Thus, every grid graph has a separator formula_12 of size at most formula_62, the removal of which partitions it into two connected components, each of size at most formula_55. 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 formula_1 but may be larger than formula_60, the bound on the size of the two subsets formula_11 and formula_13 (in the most common versions of the theorem) is formula_4 rather than formula_55, and the two subsets formula_11 and formula_13 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 formula_72, and  partition the vertices into levels by their distance from formula_72. If formula_74 is the median level (the level such that the numbers of vertices at higher and lower levels are both at most formula_55) then there must be levels formula_76 and formula_77 that are formula_1 steps above and below formula_74 respectively and that contain formula_1 vertices, respectively, for otherwise there would be more than formula_2 vertices in the levels near formula_74. They show that there must be a separator formula_12 formed by the union of formula_76 and formula_77, the endpoints of an edge formula_86 of formula_10 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 formula_86 back up to level formula_76. The size of the separator formula_12 constructed in this way is at most formula_91. 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 formula_11, formula_12, and formula_13 such that  formula_11 and formula_13 each have at most formula_40 of the total cost and formula_12 has formula_1 vertices, with no edges from formula_11 and formula_13. By analysing a similar separator construction more carefully, shows that the bound on the size of formula_12 can be reduced to formula_103. 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 formula_4 vertices. proves  this (with a separator size of formula_107) by using the Lipton–Tarjan technique for a modified version of breadth first search in which the levels of the search form simple cycles. 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 formula_126 disks touching or inside  it, at most formula_126 disks touching or outside it, and that crosses formula_1 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 formula_126 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 formula_2 non-negative real numbers is bounded by a constant, the sum of the numbers themselves is formula_1. Therefore, the expected number of disks crossed by  a random plane is formula_1 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 formula_1 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 formula_126 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 formula_135 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 formula_136. 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. Spectral clustering methods, in which the vertices of a graph are grouped by the coordinates of the eigenvectors of matrices derived from the graph, have long  been used as a heuristic for graph partitioning problems for nonplanar graphs. As show, spectral clustering can also be used to derive an alternative proof for a weakened form of the planar separator theorem that applies to planar graphs with bounded degree. In their method, the vertices of a given planar graph are sorted by the second coordinates of the eigenvectors of the Laplacian matrix of the graph, and this sorted order is partitioned at the point that minimizes the ratio of the number of edges cut by the partition to the number of vertices on the smaller side of  the partition. As they show, every planar graph of bounded degree has a partition of this type in which the ratio is formula_137. Although this partition may not be balanced, repeating the partition within the larger of the two sides and taking the union of the cuts formed at each repetition will eventually lead to a balanced partition with formula_1 edges. The endpoints of these edges form a separator of size formula_1. Edge separators. A variation of the planar separator theorem involves edge separators, small sets of edges forming a cut between two subsets formula_11 and formula_13 of the vertices  of the graph. The two sets formula_11 and formula_13 must each have size at most a constant fraction of the number formula_2 of vertices of the graph (conventionally, both sets have size at most formula_4), and each vertex of the graph belongs to exactly one of formula_11 and formula_13. The separator consists of the edges that have one endpoint in formula_11 and one endpoint in formula_13. Bounds on the size of an edge separator involve the degree of the vertices as well as the number of vertices in the graph: the planar graphs in which one vertex has degree formula_150 , including the wheel graphs and star graphs, have no edge separator with a sublinear number of edges, because any edge separator would have to include all the edges connecting the high degree vertex to the vertices on the other side of the cut. However, every planar graph with maximum degree formula_151 has an edge separator of size formula_152. A simple cycle separator in the dual graph of a planar graph forms an edge separator in the original graph. Applying the simple cycle separator theorem of to the dual graph of a given planar graph strengthens the formula_152 bound for the  size of an edge separator by showing that every planar graph has an edge separator whose size is proportional to the Euclidean norm of its vector of vertex degrees. Lower bounds. In a formula_156 grid graph, a set formula_12 of formula_158 points can enclose a subset of at most formula_159 grid points, where the maximum is achieved by arranging formula_12 in a diagonal line near a corner of the grid. Therefore, in order to form a separator that separates at least formula_29 of the points from the remaining grid, formula_162 needs to be at least formula_163. There exist formula_2-vertex  planar graphs (for arbitrarily large values of formula_2) such that, for every separator formula_12 that partitions the remaining graph into subgraphs of at most formula_4 vertices, formula_12 has at least formula_169. The construction involves approximating a sphere by a convex polyhedron, replacing each of the faces of the polyhedron by a triangular mesh, and applying isoperimetric theorems for the surface of the sphere. Separator hierarchies. Separators may be combined into a separator hierarchy of a planar graph, a recursive decomposition into smaller graphs. A separator hierarchy may be represented by a binary tree in which the root node represents the  given graph itself, and the two children of the root are the roots of recursively constructed separator hierarchies for the induced subgraphs formed from the two subsets formula_11 and formula_13 of a separator. A separator hierarchy of this type forms the basis for a tree decomposition of the given graph, in which the set of vertices associated with each tree node is the union of the separators on the path from that node to the root of the tree. Since the sizes of the graphs go down by a constant factor at each level of the tree, the upper bounds  on the sizes of the separators also go down by a constant factor at each level, so the sizes of the separators on these paths add in a geometric series to formula_1. That is, a separator formed in this way has width formula_1, and can be used to show that every planar graph has treewidth formula_1. Constructing a separator hierarchy directly, by traversing the binary tree top down and applying a linear-time planar separator algorithm to each of the induced subgraphs associated with each node of the binary tree, would take a total of formula_175 time. However, it is  possible to construct an entire separator hierarchy in linear time, by using the Lipton–Tarjan breadth-first layering approach and by using appropriate data structures to perform each partition step in sublinear time. If one forms a related type of hierarchy based on separations instead of separators, in which the two children of the root node are roots of recursively constructed hierarchies for the two subgraphs formula_27 and formula_28 of a separation of the given graph, then the overall structure forms a branch-decomposition instead of a tree decomposition. The width of any separation in this decomposition is, again, bounded  by the sum of the sizes of the separators on a path from any node to the root of the hierarchy, so any branch-decomposition formed in this way has width formula_1 and any planar graph has branchwidth formula_1. Although many other related graph partitioning problems are NP-complete, even for planar graphs, it is possible to find a minimum-width branch-decomposition of a planar graph in polynomial time. By applying methods of more directly in the construction of branch-decompositions, show that every planar graph has branchwidth at most formula_180, with the same constant as the one in  the simple cycle separator theorem of Alon et al. Since the treewidth of any graph is at most formula_181 its branchwidth, this also shows that planar graphs have treewidth at most formula_182. Other classes of graphs. Some sparse graphs do not have separators of sublinear size: in an expander graph, deleting up to a constant fraction of the vertices still leaves only one connected component. Possibly the earliest known separator theorem is a result of that any tree can be partitioned into subtrees of at most formula_55 vertices each by the removal of a single vertex. In particular, the vertex  that minimizes the maximum component size has this property, for if it did not then its neighbor in the unique large subtree would form an even better partition. By applying the same technique to a tree decomposition of an arbitrary graph, it is possible to show that any graph has a separator of size at most equal to its treewidth. If a graph formula_10 is not planar, but can be embedded on a surface of genus formula_185, then it has a separator with formula_186 vertices. prove this by using a similar approach to that of . They group the vertices of  the graph into breadth-first levels and find two levels the removal of which leaves at most one large component consisting of a small number of levels. This remaining component can be made planar by removing a number of breadth-first paths proportional to the genus, after which the Lipton–Tarjan method can be applied to the remaining planar graph. The result follows from a careful balancing of the size of the removed two levels against the number of levels between them. If the graph embedding is given as part of the input, its separator can be found in linear  time. Graphs of genus formula_185 also have edge separators of size formula_188. Graphs of bounded genus form an example of a family of graphs closed under the operation of taking minors, and separator theorems also apply to arbitrary minor-closed graph families. In particular, if a graph family has a forbidden minor with formula_189 vertices, then it has a separator with formula_190 vertices, and such a separator can be found in time formula_191 for any formula_192. The circle separator method of generalizes to the intersection graphs of any system of formula_193-dimensional balls with the property that any point in  space is covered by at most some constant number formula_194 of balls, to formula_194-nearest-neighbor graphs in formula_193 dimensions, and to the graphs arising from finite element meshes. The sphere separators constructed in this way partition the input graph into subgraphs of at most formula_197 vertices. The size of the separators for formula_194-ply ball intersection graphs and for formula_194-nearest-neighbor graphs is formula_200. If a hereditary family of graphs has a separator theorem with separators of size formula_201, for some formula_202, then it necessarily has polynomial expansion, a polynomial bound on the density of its shallow minors . Conversely, graphs with polynomial expansion have sublinear separator theorems. Applications. Divide and conquer algorithms. Separator decompositions can be of use in designing efficient divide and conquer algorithms for solving problems on planar graphs. As an example, one problem that can be solved in this way is to find the shortest cycle in a weighted planar digraph. This may be solved by the following steps: The time for the two recursive calls to formula_11 and formula_13 in this algorithm is dominated by the time to perform the formula_1 calls to Dijkstra's algorithm, so this algorithm finds the shortest cycle in  formula_216 time. A faster algorithm for the same shortest cycle problem, running in time formula_217, was given by . His algorithm uses the same separator-based divide and conquer structure, but uses simple cycle separators rather than arbitrary separators, so that the vertices of formula_12 belong to a single face of the graphs inside and outside the cycle separator. He then replaces the formula_1 separate calls to Dijkstra's algorithm with more sophisticated algorithms to find shortest paths from all vertices on a single face of a planar graph and to combine the distances from the two subgraphs. For weighted but  undirected planar graphs, the shortest cycle is equivalent to the minimum cut in the dual graph and can be found in formula_220 time, and the shortest cycle in an unweighted undirected planar graph (its girth) may be found in time formula_221. (However, the faster algorithm for unweighted graphs is not based on the separator theorem.) Frederickson proposed another faster algorithm for single source shortest paths by implementing separator theorem in planar graphs. This is an improvement of Dijkstra's algorithm with iterative search on a carefully selected subset of the vertices. This version takes formula_222 time in an formula_2-vertex  graph. Separators are used to find a division of a graph, that is, a partition of the edge-set into two or more subsets, called regions. A node is said to be contained in a region if some edge of the region is incident to the node. A node contained in more than one region is called a boundary node of the regions containing it. The method uses the notion of a formula_42-division of an formula_2-node graph that is a graph division into formula_226 regions, each containing formula_227 nodes including formula_228 boundary nodes. Frederickson showed that an formula_42 -division can be found in formula_175 time by recursive application of separator theorem. The sketch of his algorithm to solve the problem is as follows. Henzinger et al. extended Frederickson's formula_42-division technique for the single source shortest path algorithm in planar graphs for nonnegative edge-lengths and proposed a linear time algorithm. Their method generalizes Frederickson's notion of graph-divisions such that now an formula_245-division of an formula_2-node graph is a division into formula_226 regions, each containing formula_248 nodes, each having at most formula_162 boundary nodes. If an formula_245-division is repeatedly divided into smaller  regions, that is called a recursive division. This algorithm uses approximately formula_251 levels of divisions, where formula_252 denotes the iterated logarithm function. The recursive division is represented by a rooted tree whose leaves are labeled by distinct edge of formula_10. The root of the tree represents the region consisting of all of formula_10, the children of the root represent the subregions into which that region is divided and so on. Each leaf (atomic region) represents a region containing exactly one edge. Nested dissection is a separator based divide and conquer variation of Gaussian elimination for solving sparse symmetric systems of  linear equations with a planar graph structure, such as the ones arising from the finite element method. It involves finding a separator for the graph describing the system of equations, recursively eliminating the variables in the two subproblems separated from each other by the separator, and then eliminating the variables in the separator. The fill-in of this method (the number of nonzero coefficients of the resulting Cholesky decomposition of the matrix) is formula_175, allowing this method to be competitive with iterative methods for the same problems. Klein, Mozes and Weimann gave an formula_256-time, linear-space algorithm to find  the shortest path distances from a source vertex formula_162 to all other vertices for a directed planar graph with positive and negative arc-lengths containing no negative cycles. Their algorithm uses planar graph separators to find a Jordan curve formula_108 that passes through formula_1 nodes (and no arcs) such that between formula_29 and formula_4 nodes are enclosed by formula_108. Nodes through which formula_108 passes are boundary nodes. The original graph formula_10 is separated into two subgraphs formula_231 and formula_27 by cutting the planar embedding along formula_108 and duplicating the boundary nodes. The boundary nodes in each graph formula_268 lie on  the boundary of a single face formula_269. The overview of their approach is given below. An important part of this algorithm is the use of price functions and reduced lengths. For a directed graph formula_10 with arc-lengths formula_293, a price function is a function formula_294 from the nodes of formula_10 to the real numbers. For an arc formula_296, the reduced length with respect to formula_294 is formula_298. A feasible price function is a price function that induces nonnegative reduced lengths on all arcs of formula_10. It is useful in transforming a shortest-path problem involving positive and negative lengths  into one involving only nonnegative lengths, which can then be solved using Dijkstra's algorithm. The separator based divide and conquer paradigm has also been used to design data structures for dynamic graph algorithms and point location, algorithms for polygon triangulation, shortest paths, and the construction of nearest neighbor graphs, and approximation algorithms for the maximum independent set of a planar graph. Exact solution of NP-hard optimization problems. By using dynamic programming on a tree decomposition or branch-decomposition of a planar graph, many NP-hard optimization problems may be solved in time exponential in formula_60 or formula_301. For  instance, bounds of this form are known for finding maximum independent sets, Steiner trees, and Hamiltonian cycles, and for solving the travelling salesman problem on planar graphs. Similar methods involving separator theorems for geometric graphs may be used to solve Euclidean travelling salesman problem and Steiner tree construction problems in time bounds of the same form. For parameterized problems that admit a kernelization that preserves planarity and reduces the input graph to a kernel of size linear in the input parameter, this approach can be used to design fixed-parameter tractable algorithms the running time of which depends polynomially on  the size of the input graph and exponentially on formula_302, where formula_194 is the parameter of the algorithm. For instance, time bounds of this form are known for finding vertex covers and dominating sets of size formula_194. Approximation algorithms. observed that the separator theorem may be used to obtain polynomial time approximation schemes for NP-hard optimization problems on planar graphs such as finding the maximum independent set. Specifically, by truncating a separator hierarchy at an appropriate level, one may find a separator of size formula_305 the removal of which partitions the graph into subgraphs of size at most formula_306 , for any constant formula_43. By the four-color theorem, there exists an independent set of size at least formula_308, so the removed nodes form a negligible fraction of the maximum independent set, and the maximum independent sets in the remaining subgraphs can be found independently in time exponential in their size. By combining this approach with later linear-time methods for separator hierarchy construction and with table lookup to share the computation of independent sets between isomorphic subgraphs, it can be made to construct independent sets of size within a factor of formula_309 of optimal, in linear time. However, for  approximation ratios even closer to one than this factor, a later approach of (based on tree-decomposition but not on planar separators) provides better tradeoffs of time versus approximation quality. Similar separator-based approximation schemes have also been used to approximate other hard problems such as vertex cover. use separators in a different way to approximate the travelling salesman problem for the shortest path metric on weighted planar graphs; their algorithm uses dynamic programming to find the shortest tour that, at each level of a separator hierarchy, crosses the separator a bounded number of times, and they show that as  the crossing bound increases the tours constructed in this way have lengths that approximate the optimal tour. Graph compression. Separators have been used as part of data compression algorithms for representing planar graphs and other separable graphs using a small number of bits. The basic principle of these algorithms is to choose a number formula_194 and repeatedly subdivide the given planar graph using separators into formula_311 subgraphs of size at most formula_194, with formula_313 vertices in the separators. With an appropriate choice of formula_194 (at most proportional to the logarithm of formula_2) the number of non-isomorphic formula_194-vertex planar  subgraphs is significantly less than the number of subgraphs in the decomposition, so the graph can be compressed by constructing a table of all the possible non-isomorphic subgraphs and representing each subgraph in the separator decomposition by its index into the table. The remainder of the graph, formed by the separator vertices, may be represented explicitly or by using a recursive version of the same data structure. Using this method, planar graphs and many more restricted families of graphs may be encoded using a number of bits that is information-theoretically optimal: if there are formula_317 formula_2-vertex graphs  in the family of graphs to be represented, then an individual graph in the family can be represented using only formula_319 bits. It is also possible to construct representations of this type in which one may test adjacency between vertices, determine the degree of a vertex, and list neighbors of vertices in constant time per query, by augmenting the table of subgraphs with additional tabular information representing the answers to the queries. Universal graphs. A universal graph for a family formula_320 of graphs is a graph that contains every member of formula_320 as a subgraphs. Separators can be used to  show that the formula_2-vertex planar graphs have universal graphs with formula_2 vertices and formula_324 edges. The construction involves a strengthened form of the separator theorem in which the size of the three subsets of vertices in the separator does not depend on the graph structure: there exists a number formula_43, the magnitude of which at most a constant times formula_60, such that the vertices of every formula_2-vertex planar graph can be separated into subsets formula_11, formula_12, and formula_13, with no edges from formula_11 to formula_13, with formula_333, and with formula_334. This may be shown by using the usual  form of the separator theorem repeatedly to partition the graph until all the components of the partition can be arranged into two subsets of fewer than formula_55 vertices, and then moving vertices from these subsets into the separator as necessary until it has the given size. Once a separator theorem of this type is shown, it can be used to produce a separator hierarchy for formula_2-vertex planar graphs that again does not depend on the graph structure: the tree-decomposition formed from this hierarchy has width formula_1 and can be used for any planar graph. The set of all  pairs of vertices in this tree-decomposition that both belong to a common node of the tree-decomposition forms a trivially perfect graph with formula_324 vertices that contains every formula_2-vertex planar graph as a subgraph. A similar construction shows that bounded-degree planar graphs have universal graphs with formula_175 edges, where the constant hidden in the O notation depends on the degree bound. Any universal graph for planar graphs (or even for trees of unbounded degree) must have formula_341 edges.