Planar separator theorem
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.
The existence of a separator theorem for a class of graphs can be formalized and quantified by the concepts of treewidth and polynomial expansion.
[4] This proof of the separator theorem applies as well to weighted planar graphs, in which each vertex has a non-negative cost.
[4] By analysing a similar separator construction more carefully, Djidjev (1982) shows that the bound on the size of
[2] Holzer et al. (2009) suggest a simplified version of this approach: they augment the graph to be maximal planar and construct a breadth first search tree as before.
[6] Alon, Seymour & Thomas (1994) prove the existence of simple cycle separators more directly: let
, then these matched pairs can be connected by vertex-disjoint paths within the disk, by a form of Menger's theorem for planar graphs.
With some additional work they show by a similar method that there exists a simple cycle separator of size at most
[8] 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.
[10] To prove this, Miller et al. use stereographic projection to map the packing onto the surface of a unit sphere in three dimensions.
If a plane through the center is chosen uniformly at random, a disk will be crossed with probability proportional to its radius.
Although this improved separator size bound comes at the expense of a more-uneven partition of the graph, Spielman & Teng (1996) argue that it provides an improved constant factor in the time bounds for nested dissection compared to the separators of Alon, Seymour & Thomas (1990).
The size of the separators it produces can be further improved, in practice, by using a nonuniform distribution for the random cutting planes.
Papadimitriou & Sideri (1996) describe a polynomial time algorithm for finding the smallest edge separator that partitions a graph
[21] By applying methods of Alon, Seymour & Thomas (1994) more directly in the construction of branch-decompositions, Fomin & Thilikos (2006a) show that every planar graph has branchwidth at most
[10] 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.
[26] Separator decompositions can be of use in designing efficient divide and conquer algorithms for solving problems on planar graphs.
Frederickson proposed another faster algorithm for single source shortest paths by implementing separator theorem in planar graphs.
[29] This is an improvement of Dijkstra's algorithm with iterative search on a carefully selected subset of the vertices.
The recursive division is represented by a rooted tree whose leaves are labeled by distinct edge of
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.
[31] The fill-in of this method (the number of nonzero coefficients of the resulting Cholesky decomposition of the matrix) is
[35] 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
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.
For instance, time bounds of this form are known for finding vertex covers and dominating sets of size
[40] Lipton & Tarjan (1980) 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.
[41] Arora et al. (1998) 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.
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.
[42] 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.
