Planar separator theorem
Encyclopedia
In graph theory
, the planar separator theorem is a form of isoperimetric inequality for planar graph
s, 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 (where the O invokes big O notation
) 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 , 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 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. Separator hierarchies may be used to devise efficient divide and conquer algorithm
s 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 method
s.
An equivalent formulation is that the edges of any n-vertex planar graph G may be subdivided into two edge-disjoint subgraphs G1 and G2 in such a way that both subgraphs have at least n/3 vertices and such that the intersection of the vertex sets of the two subgraphs has O(√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 the separated subsets of at most 2n/3 vertices. In the other direction, if one is given a partition into three sets A, S, and B that meet the conditions of the planar separator theorem, then one may form a separation in which the edges with an endpoint in A belong to G1, the edges with an endpoint in B belong to G2, and the remaining edges (with both endpoints in S) are partitioned arbitrarily.
The constant 2/3 in the statement of the separator theorem is arbitrary and may be replaced by any other number in the open interval (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.
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.
, rooted at an arbitrary vertex v, and partition the vertices into levels by their distance from v. If l1 is the median
level (the level such that the numbers of vertices at higher and lower levels are both at most n/2) then there must be levels l0 and l2 that are O(√n) steps above and below l1 respectively and that contain O(√n) vertices, respectively, for otherwise there would be more than n vertices in the levels near l1. They show that there must be a separator S formed by the union of l0 and l2, the endpoints e of an edge of G 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 e back up to level l0. The size of the separator S constructed in this way is at most √8√n, or approximately 2.83√n. 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 A, S, and B such that A and B each have at most 2/3 of the total cost and S has O(√n) vertices, with no edges from A to B. By analysing a similar separator construction more carefully, shows that the bound on the size of S can be reduced to √6√n, or approximately 2.45√n.
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 e that is not part of the tree, they form a cycle by combining e 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.
prove the existence of simple cycle separators more directly: they let C be a cycle of at most √8√n vertices, with at most 2n/3 vertices outside C, that forms as even a partition of inside and outside as possible, and they show that these assumptions force C to be a separator. For otherwise, the distances within C must equal the distances in the disk enclosed by C (a shorter path through the interior of the disk would form part of the boundary of a better cycle). Additionally, C must have length exactly √8√n, as otherwise it could be improved by replacing one of its edges by the other two sides of a triangle. If the vertices in C are numbered (in clockwise order) from 1 to √8√n, and vertex i 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 n, a contradiction. With some additional work they show by a similar method that there exists a simple cycle separator of size at most (3/√2)√n, approximately 2.12√n.
further improved the constant factor in the simple cycle separator theorem to 1.97√n. Their method can also find simple cycle separators for graphs with non-negative vertex weights, with separator size at most 2√n, and can generate separators with smaller size at the expense of a more uneven partition of the graph. In 2-connected 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.
, 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 3n/4 disks touching or inside it, at most 3n/4 disks touching or outside it, and that crosses O(√n 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 3n/4 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 n non-negative real numbers is bounded by a constant, the sum of the numbers themselves is O(√n). Therefore, the expected number of disks crossed by a random plane is O(√n) 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 O(√n) 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 3n/4 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 packing
s, 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.
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 O(1/√n). 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 O(√n) edges. The endpoints of these edges form a separator of size O(√n).
between two subsets A and B of the vertices of the graph. The two sets A and B must each have size at most a constant fraction of the number n of vertices of the graph (conventionally, both sets have size at most 2n/3), and each vertex of the graph belongs to exactly one of A and B. The separator consists of the edges that have one endpoint in A and one endpoint in B. 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 n − 1, including the wheel graph
s 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 Δ has an edge separator of size O(√(Δn)).
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 O(√(Δn)) 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.
describe a polynomial time algorithm for finding the smallest edge separator that partitions a graph G into two subgraphs of equal size, when G is an induced subgraph of a grid graph with no holes or with a constant number of holes. However, they conjecture that the problem is NP-complete
for arbitrary planar graphs, and they show that the complexity of the problem is the same for grid graphs with arbitrarily many holes as it is for arbitrary planar graphs.
There exist n-vertex planar graphs (for arbitrarily large values of n) such that, for every separator S that partitions the remaining graph into subgraphs of at most 2n/3 vertices, S has at least √(4π√3)√n vertices, approximately 1.56√n. 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.
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 A and B 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 O(√n). That is, a separator formed in this way has width O(√n), and can be used to show that every planar graph have treewidth O(√n).
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 O(n log n) 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 structure
s 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 G1 and G2 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 O(√n) and any planar graph has branchwidth O(√n). 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 2.12√n, 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 3/2 its branchwidth, this also shows that planar graphs have treewidth at most 3.18√n.
, 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 2n/3 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 G is not planar, but can be embedded
on a surface of genus
g, then it has a separator with O((gn)1/2) 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 g also have edge separators of size O((gΔn)1/2).
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 h vertices, then it has a separator with O(h√n) vertices, and such a separator can be found in time O(n1 + ε) for any ε > 0.
The circle separator method of generalizes to the intersection graphs of any system of d-dimensional balls with the property that any point in space is covered by at most some constant number k of balls, to k-nearest-neighbor graphs in d 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 vertices. The size of the separators for k-ply ball intersection graphs and for k-nearest-neighbor graphs is O(k1/dn1 − 1/d).
s 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 A and B in this algorithm is dominated by the time to perform the O(√n) calls to Dijkstra's algorithm, so this algorithm finds the shortest cycle in O(n3/2 log n) time.
A faster algorithm for the same shortest cycle problem, running in time O(n log3n), 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 S belong to a single face of the graphs inside and outside the cycle separator. He then replaces the O(√n) 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 O(n log2n) time, and the shortest cycle in an unweighted undirected planar graph (its girth) may be found in time O(n), but although these algorithms both use a similar divide and conquer strategy the divide parts of the algorithms are not based on the separator theorem.
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 O(n log n), allowing this method to be competitive with iterative methods for the same problems.
The separator based divide and conquer paradigm has also been used to design data structure
s for dynamic graph algorithms
and point location
, algorithms for polygon triangulation
, shortest paths, and the construction of nearest neighbor graph
s, and approximation algorithm
s for the maximum independent set of a planar graph.
on a tree decomposition
or branch-decomposition
of a planar graph, many NP-hard
optimization problems may be solved in time exponential in √n or √n log n. For instance, bounds of this form are known for finding maximum independent sets, Steiner tree
s, 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 √k, where k is the parameter of the algorithm. For instance, time bounds of this form are known for finding vertex cover
s and dominating set
s of size k.
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 O(n/√log n) the removal of which partitions the graph into subgraphs of size c log n, for any constant c. By the four-color theorem, there exists an independent set of size at least n/4, 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 1 − O(1/√log n) of optimal, in linear time. However, for approximation ratios even closer to 1 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.
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 k and repeatedly subdivide the given planar graph using separators into O(n/k) subgraphs of size at most k, with O(n/√k) vertices in the separators. With an appropriate choice of k (at most proportional to the logarithm
of n) the number of non-isomorphic
k-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 planar graphs may be encoded using a number of bits that is information-theoretically
optimal: if there are Pn n-vertex graphs in the family of graphs to be represented, then an individual graph in the family can be represented using only (1 + o(n))log2Pn 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.
for a family F of graphs is a graph that contains every member of F as a subgraphs. Separators can be used to show that the n-vertex planar graphs have universal graphs with n vertices and O(n3/2) 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 c, the magnitude of which at most a constant times √n, such that the vertices of every n-vertex planar graph can be separated into subsets A, S, and B, with no edges from A to B, with |S| = c, and with |A| = |B| = (n − c)/2. 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 n/2 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 n-vertex planar graphs that again does not depend on the graph structure: the tree-decomposition formed from this hierarchy has width O(√n) 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 O(n3/2) vertices that contains every n-vertex planar graph as a subgraph. A similar construction shows that bounded-degree planar graphs have universal graphs with O(n log n) 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 Ω(n log n) edges, but it remains unknown whether this lower bound or the O(n3/2) upper bound is tight for universal graphs for arbitrary planar graphs.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the planar separator theorem is a form of isoperimetric inequality for planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s, 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 (where the O invokes big O notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
) can partition
Graph partition
In mathematics, the graph partition problem is defined on data represented in the form of a graph G= , with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way partition divides the vertex set into k smaller...
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 , 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 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
Tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph...
or a branch-decomposition
Branch-decomposition
In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves...
of the graph. Separator hierarchies may be used to devise efficient divide and conquer algorithm
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
s for planar graphs, and dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
on these hierarchies can be used to devise exponential time and fixed-parameter tractable algorithms for solving NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
optimization problems on these graphs. Separator hierarchies may also be used in nested dissection
Nested dissection
In numerical analysis, nested dissection is a divide and conquer heuristic for the solution of sparse symmetric systems of linear equations based on graph partitioning...
, an efficient variant of Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
for solving sparse
Sparse matrix
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
systems of linear equations arising from finite element method
Finite element method
The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...
s.
Statement of the theorem
As it is usually stated, the separator theorem states that, in any n-vertex planar graph G = (V,E), there exists a partition of the vertices of G into three sets A, S, and B, such that each of A and B has at most 2n/3 vertices, S has O(√n) vertices, and there are no edges with one endpoint in A and one endpoint in B. It is not required that A or B form connected subgraphs of G. S is called the separator for this partition.An equivalent formulation is that the edges of any n-vertex planar graph G may be subdivided into two edge-disjoint subgraphs G1 and G2 in such a way that both subgraphs have at least n/3 vertices and such that the intersection of the vertex sets of the two subgraphs has O(√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 the separated subsets of at most 2n/3 vertices. In the other direction, if one is given a partition into three sets A, S, and B that meet the conditions of the planar separator theorem, then one may form a separation in which the edges with an endpoint in A belong to G1, the edges with an endpoint in B belong to G2, and the remaining edges (with both endpoints in S) are partitioned arbitrarily.
The constant 2/3 in the statement of the separator theorem is arbitrary and may be replaced by any other number in the open interval (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.
Example
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.
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 searchBreadth-first search
In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
, rooted at an arbitrary vertex v, and partition the vertices into levels by their distance from v. If l1 is the median
Median
In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...
level (the level such that the numbers of vertices at higher and lower levels are both at most n/2) then there must be levels l0 and l2 that are O(√n) steps above and below l1 respectively and that contain O(√n) vertices, respectively, for otherwise there would be more than n vertices in the levels near l1. They show that there must be a separator S formed by the union of l0 and l2, the endpoints e of an edge of G 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 e back up to level l0. The size of the separator S constructed in this way is at most √8√n, or approximately 2.83√n. 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 A, S, and B such that A and B each have at most 2/3 of the total cost and S has O(√n) vertices, with no edges from A to B. By analysing a similar separator construction more carefully, shows that the bound on the size of S can be reduced to √6√n, or approximately 2.45√n.
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 e that is not part of the tree, they form a cycle by combining e 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 2n/3 vertices. proves this (with a separator size of √8√n) 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: they let C be a cycle of at most √8√n vertices, with at most 2n/3 vertices outside C, that forms as even a partition of inside and outside as possible, and they show that these assumptions force C to be a separator. For otherwise, the distances within C must equal the distances in the disk enclosed by C (a shorter path through the interior of the disk would form part of the boundary of a better cycle). Additionally, C must have length exactly √8√n, as otherwise it could be improved by replacing one of its edges by the other two sides of a triangle. If the vertices in C are numbered (in clockwise order) from 1 to √8√n, and vertex i 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
Menger's theorem
In the mathematical discipline of graph theory and related areas, Menger's theorem is a basic result about connectivity in finite undirected graphs. It was proved for edge-connectivity and vertex-connectivity by Karl Menger in 1927...
for planar graphs. However, the total length of these paths would necessarily exceed n, a contradiction. With some additional work they show by a similar method that there exists a simple cycle separator of size at most (3/√2)√n, approximately 2.12√n.
further improved the constant factor in the simple cycle separator theorem to 1.97√n. Their method can also find simple cycle separators for graphs with non-negative vertex weights, with separator size at most 2√n, and can generate separators with smaller size at the expense of a more uneven partition of the graph. In 2-connected 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 theoremCircle packing theorem
The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint...
, 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 3n/4 disks touching or inside it, at most 3n/4 disks touching or outside it, and that crosses O(√n disks).
To prove this, Miller et al. use stereographic projection
Stereographic projection
The stereographic projection, in geometry, is a particular mapping that projects a sphere onto a plane. The projection is defined on the entire sphere, except at one point — the projection point. Where it is defined, the mapping is smooth and bijective. It is conformal, meaning that it...
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
Centerpoint (geometry)
In statistics and computational geometry, the notion of centerpoint is a generalization of the median to data in higher-dimensional Euclidean space...
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 3n/4 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
Jensen's inequality
In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906. Given its generality, the inequality appears in many forms depending on the context,...
shows that, when the sum of squares of n non-negative real numbers is bounded by a constant, the sum of the numbers themselves is O(√n). Therefore, the expected number of disks crossed by a random plane is O(√n) and there exists a plane that crosses at most that many disks. This plane intersects the sphere in a great circle
Great circle
A great circle, also known as a Riemannian circle, of a sphere is the intersection of the sphere and a plane which passes through the center point of the sphere, as opposed to a general circle of a sphere where the plane is not required to pass through the center...
, which projects back down to a circle in the plane with the desired properties. The O(√n) 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 3n/4 vertices in each of these two subsets.
This method leads to a randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
that finds such a separator in linear time, and a less-practical deterministic algorithm
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
with the same linear time bound. By analyzing this algorithm carefully using known bounds on the packing density
Packing problem
Packing problems are a class of optimization problems in mathematics which involve attempting to pack objects together , as densely as possible. Many of these problems can be related to real life packaging, storage and transportation issues...
of circle packing
Circle packing
In geometry, circle packing is the study of the arrangement of circles on a given surface such that no overlapping occurs and so that all circles touch another. The associated "packing density", η of an arrangement is the proportion of the surface covered by the circles...
s, 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.
Spectral partitioning
Spectral clustering methods, in which the vertices of a graph are grouped by the coordinates of the eigenvectors of matricesMatrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
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
Laplacian matrix
In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be...
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 O(1/√n). 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 O(√n) edges. The endpoints of these edges form a separator of size O(√n).
Edge separators
A variation of the planar separator theorem involves edge separators, small sets of edges forming a cutCut (graph theory)
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.In an unweighted undirected graph, the...
between two subsets A and B of the vertices of the graph. The two sets A and B must each have size at most a constant fraction of the number n of vertices of the graph (conventionally, both sets have size at most 2n/3), and each vertex of the graph belongs to exactly one of A and B. The separator consists of the edges that have one endpoint in A and one endpoint in B. Bounds on the size of an edge separator involve the degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
of the vertices as well as the number of vertices in the graph: the planar graphs in which one vertex has degree n − 1, including the wheel graph
Wheel graph
In the mathematical discipline of graph theory, a wheel graph Wn is a graph with n vertices, formed by connecting a single vertex to all vertices of an -cycle. The numerical notation for wheels is used inconsistently in the literature: some authors instead use n to refer to the length of the cycle,...
s and star graphs
Star (graph theory)
In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...
, 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 Δ has an edge separator of size O(√(Δn)).
A simple cycle separator in the dual graph
Dual graph
In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual...
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 O(√(Δn)) 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.
describe a polynomial time algorithm for finding the smallest edge separator that partitions a graph G into two subgraphs of equal size, when G is an induced subgraph of a grid graph with no holes or with a constant number of holes. However, they conjecture that the problem is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
for arbitrary planar graphs, and they show that the complexity of the problem is the same for grid graphs with arbitrarily many holes as it is for arbitrary planar graphs.
Lower bounds
In a √n × √n grid graph, a set S of s < √n points can enclose a subset of at most s(s − 1)/2 grid points, where the maximum is achieved by arranging S in a diagonal line near a corner of the grid. Therefore, in order to form a separator that separates at least n/3 of the points from the remaining grid, s needs to be at least √(2n/3), approximately 0.82√n.There exist n-vertex planar graphs (for arbitrarily large values of n) such that, for every separator S that partitions the remaining graph into subgraphs of at most 2n/3 vertices, S has at least √(4π√3)√n vertices, approximately 1.56√n. The construction involves approximating a sphere
Sphere
A sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...
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 treeBinary tree
In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
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 A and B of a separator.
A separator hierarchy of this type forms the basis for a tree decomposition
Tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph...
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 O(√n). That is, a separator formed in this way has width O(√n), and can be used to show that every planar graph have treewidth O(√n).
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 O(n log n) 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 structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s 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 G1 and G2 of a separation of the given graph, then the overall structure forms a branch-decomposition
Branch-decomposition
In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves...
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 O(√n) and any planar graph has branchwidth O(√n). Although many other related graph partitioning problems are NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, 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 2.12√n, 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 3/2 its branchwidth, this also shows that planar graphs have treewidth at most 3.18√n.
Other classes of graphs
Some sparse graphs do not have separators of sublinear size: in an expander graphExpander graph
In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...
, 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
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
can be partitioned into subtrees of at most 2n/3 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
Tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph...
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 G is not planar, but can be embedded
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
on a surface of genus
Genus (mathematics)
In mathematics, genus has a few different, but closely related, meanings:-Orientable surface:The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected. It...
g, then it has a separator with O((gn)1/2) 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 g also have edge separators of size O((gΔn)1/2).
Graphs of bounded genus form an example of a family of graphs closed under the operation of taking minors
Minor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
, and separator theorems also apply to arbitrary minor-closed graph families. In particular, if a graph family has a forbidden minor with h vertices, then it has a separator with O(h√n) vertices, and such a separator can be found in time O(n1 + ε) for any ε > 0.
Finite element method
The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...
. The sphere separators constructed in this way partition the input graph into subgraphs of at most vertices. The size of the separators for k-ply ball intersection graphs and for k-nearest-neighbor graphs is O(k1/dn1 − 1/d).
Divide and conquer algorithms
Separator decompositions can be of use in designing efficient divide and conquer algorithmDivide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
s for solving problems on planar graphs. As an example, one problem that can be solved in this way is to find the shortest cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
in a weighted planar digraph. This may be solved by the following steps:
- Partition the given graph G into three subsets S, A, B according to the planar separator theorem
- Recursively search for the shortest cycles in A and B
- Use Dijkstra's algorithmDijkstra's algorithmDijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
to find, for each s in S, the shortest cycle through s in G. - Return the shortest of the cycles found by the above steps.
The time for the two recursive calls to A and B in this algorithm is dominated by the time to perform the O(√n) calls to Dijkstra's algorithm, so this algorithm finds the shortest cycle in O(n3/2 log n) time.
A faster algorithm for the same shortest cycle problem, running in time O(n log3n), 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 S belong to a single face of the graphs inside and outside the cycle separator. He then replaces the O(√n) 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
Minimum cut
In graph theory, a minimum cut of a graph is a cut whose cutset has the smallest number of elements or smallest sum of weights possible...
in the dual graph
Dual graph
In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual...
and can be found in O(n log2n) time, and the shortest cycle in an unweighted undirected planar graph (its girth) may be found in time O(n), but although these algorithms both use a similar divide and conquer strategy the divide parts of the algorithms are not based on the separator theorem.
Nested dissection
Nested dissection
In numerical analysis, nested dissection is a divide and conquer heuristic for the solution of sparse symmetric systems of linear equations based on graph partitioning...
is a separator based divide and conquer variation of Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
for solving sparse
Sparse matrix
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
symmetric systems of linear equations with a planar graph structure, such as the ones arising from the finite element method
Finite element method
The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...
. 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
Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky triangle is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André-Louis Cholesky for real matrices...
of the matrix) is O(n log n), allowing this method to be competitive with iterative methods for the same problems.
The separator based divide and conquer paradigm has also been used to design data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s for dynamic graph algorithms
Dynamic problem (algorithms)
Dynamic problems in computational complexity theory are problems stated in terms of the changing input data. In the most general form a problem in this category is usually stated as follows:...
and point location
Point location
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems , motion planning, and computer aided design ....
, algorithms for polygon triangulation
Polygon triangulation
In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
, shortest paths, and the construction of nearest neighbor graph
Nearest neighbor graph
The nearest neighbor graph for a set of n objects P in a metric space is a directed graph with P being its vertex set and with a directed edge from p to q whenever q is a nearest neighbor of p The nearest neighbor graph (NNG) for a set of n objects P in a metric space (e.g., for a set of points...
s, and approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
s for the maximum independent set of a planar graph.
Exact solution of NP-hard optimization problems
By using dynamic programmingDynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
on a tree decomposition
Tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph...
or branch-decomposition
Branch-decomposition
In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves...
of a planar graph, many NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
optimization problems may be solved in time exponential in √n or √n log n. For instance, bounds of this form are known for finding maximum independent sets, Steiner tree
Steiner tree
The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
s, and Hamiltonian cycles, and for solving the travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
on planar graphs. Similar methods involving separator theorems for geometric graphs may be used to solve Euclidean travelling salesman problem and Steiner tree
Steiner tree
The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
construction problems in time bounds of the same form.
For parameterized
Parameterized complexity
Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. The complexity of a problem is then measured as a function in those...
problems that admit a kernelization
Kernelization
In computer science, a kernelization is an efficient algorithm that preprocesses instances of decision problems by mapping them to equivalent instances with a guaranteed upper bound on the size of the output, called the kernel of the instance. Kernelization is often achieved by applying a set of...
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 √k, where k is the parameter of the algorithm. For instance, time bounds of this form are known for finding vertex cover
Vertex cover
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
s and dominating set
Dominating set
In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...
s of size k.
Approximation algorithms
observed that the separator theorem may be used to obtain polynomial time approximation schemes for NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
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 O(n/√log n) the removal of which partitions the graph into subgraphs of size c log n, for any constant c. By the four-color theorem, there exists an independent set of size at least n/4, 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
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
subgraphs, it can be made to construct independent sets of size within a factor of 1 − O(1/√log n) of optimal, in linear time. However, for approximation ratios even closer to 1 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
Vertex cover
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
. use separators in a different way to approximate the travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
for the shortest path metric
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
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 compressionData compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
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 k and repeatedly subdivide the given planar graph using separators into O(n/k) subgraphs of size at most k, with O(n/√k) vertices in the separators. With an appropriate choice of k (at most proportional to the logarithm
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
of n) the number of non-isomorphic
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
k-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 planar graphs may be encoded using a number of bits that is information-theoretically
Information theory
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
optimal: if there are Pn n-vertex graphs in the family of graphs to be represented, then an individual graph in the family can be represented using only (1 + o(n))log2Pn 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 graphUniversal graph
In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by R. Rado and is now called the Rado graph or random graph...
for a family F of graphs is a graph that contains every member of F as a subgraphs. Separators can be used to show that the n-vertex planar graphs have universal graphs with n vertices and O(n3/2) 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 c, the magnitude of which at most a constant times √n, such that the vertices of every n-vertex planar graph can be separated into subsets A, S, and B, with no edges from A to B, with |S| = c, and with |A| = |B| = (n − c)/2. 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 n/2 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 n-vertex planar graphs that again does not depend on the graph structure: the tree-decomposition formed from this hierarchy has width O(√n) 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 O(n3/2) vertices that contains every n-vertex planar graph as a subgraph. A similar construction shows that bounded-degree planar graphs have universal graphs with O(n log n) 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 Ω(n log n) edges, but it remains unknown whether this lower bound or the O(n3/2) upper bound is tight for universal graphs for arbitrary planar graphs.