Planar separator theorem

From HandWiki
Short description: Any planar graph can be subdivided by removing a few vertices

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 [math]\displaystyle{ O(\sqrt{n}) }[/math] 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 [math]\displaystyle{ 2n/3 }[/math] vertices.

A weaker form of the separator theorem with [math]\displaystyle{ O(\sqrt{n}\log^{3/2}n) }[/math] vertices in the separator instead of [math]\displaystyle{ O(\sqrt{n}) }[/math] was originally proven by (Ungar 1951), and the form with the tight asymptotic bound on the separator size was first proven by (Lipton Tarjan). Since their work, the separator theorem has been reproven in several different ways, the constant in the [math]\displaystyle{ O(\sqrt n) }[/math] 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 [math]\displaystyle{ n }[/math]-vertex planar graph [math]\displaystyle{ G=(V,E) }[/math], there exists a partition of the vertices of [math]\displaystyle{ G }[/math] into three sets [math]\displaystyle{ A }[/math], [math]\displaystyle{ S }[/math], and [math]\displaystyle{ B }[/math], such that each of [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] has at most [math]\displaystyle{ 2n/3 }[/math] vertices, [math]\displaystyle{ S }[/math] has [math]\displaystyle{ O(\sqrt n) }[/math] vertices, and there are no edges with one endpoint in [math]\displaystyle{ A }[/math] and one endpoint in [math]\displaystyle{ B }[/math]. It is not required that [math]\displaystyle{ A }[/math] or [math]\displaystyle{ B }[/math] form connected subgraphs of [math]\displaystyle{ G }[/math]. [math]\displaystyle{ S }[/math] is called the separator for this partition.

An equivalent formulation is that the edges of any [math]\displaystyle{ n }[/math]-vertex planar graph [math]\displaystyle{ G }[/math] may be subdivided into two edge-disjoint subgraphs [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math] in such a way that both subgraphs have at least [math]\displaystyle{ n/3 }[/math] vertices and such that the intersection of the vertex sets of the two subgraphs has [math]\displaystyle{ O(\sqrt n) }[/math] vertices in it. Such a partition is known as a separation.[1] 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 [math]\displaystyle{ 2n/3 }[/math] vertices. In the other direction, if one is given a partition into three sets [math]\displaystyle{ A }[/math], [math]\displaystyle{ S }[/math], and [math]\displaystyle{ B }[/math] that meet the conditions of the planar separator theorem, then one may form a separation in which the edges with an endpoint in [math]\displaystyle{ A }[/math] belong to [math]\displaystyle{ G_1 }[/math], the edges with an endpoint in [math]\displaystyle{ B }[/math] belong to [math]\displaystyle{ G_2 }[/math], and the remaining edges (with both endpoints in [math]\displaystyle{ S }[/math]) are partitioned arbitrarily.

The constant [math]\displaystyle{ 2/3 }[/math] in the statement of the separator theorem is arbitrary and may be replaced by any other number in the open interval [math]\displaystyle{ (1/2,1) }[/math] 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.[2]

Example

A planar separator for a grid graph

Consider a grid graph with [math]\displaystyle{ r }[/math] rows and [math]\displaystyle{ c }[/math] columns; the number [math]\displaystyle{ n }[/math] of vertices equals [math]\displaystyle{ rc }[/math]. For instance, in the illustration, [math]\displaystyle{ r=5 }[/math], [math]\displaystyle{ c=8 }[/math], and [math]\displaystyle{ n=rc=40 }[/math]. If [math]\displaystyle{ r }[/math] is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if [math]\displaystyle{ c }[/math] is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing [math]\displaystyle{ S }[/math] to be any of these central rows or columns, and removing [math]\displaystyle{ S }[/math] from the graph, partitions the graph into two smaller connected subgraphs [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], each of which has at most [math]\displaystyle{ n/2 }[/math] vertices. If [math]\displaystyle{ r\le c }[/math] (as in the illustration), then choosing a central column will give a separator [math]\displaystyle{ S }[/math] with [math]\displaystyle{ r\le\sqrt{n} }[/math] vertices, and similarly if [math]\displaystyle{ c\le r }[/math] then choosing a central row will give a separator with at most [math]\displaystyle{ \sqrt{n} }[/math] vertices. Thus, every grid graph has a separator [math]\displaystyle{ S }[/math] of size at most [math]\displaystyle{ \sqrt n }[/math], the removal of which partitions it into two connected components, each of size at most [math]\displaystyle{ n/2 }[/math].[3]

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 [math]\displaystyle{ O(\sqrt{n}) }[/math] but may be larger than [math]\displaystyle{ \sqrt{n} }[/math], the bound on the size of the two subsets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] (in the most common versions of the theorem) is [math]\displaystyle{ 2n/3 }[/math] rather than [math]\displaystyle{ n/2 }[/math], and the two subsets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] need not themselves form connected subgraphs.

Constructions

Breadth-first layering

(Lipton Tarjan) 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 [math]\displaystyle{ v }[/math], and partition the vertices into levels by their distance from [math]\displaystyle{ v }[/math]. If [math]\displaystyle{ l_1 }[/math] is the median level (the level such that the numbers of vertices at higher and lower levels are both at most [math]\displaystyle{ n/2 }[/math]) then there must be levels [math]\displaystyle{ l_0 }[/math] and [math]\displaystyle{ l_2 }[/math] that are [math]\displaystyle{ O(\sqrt{n}) }[/math] steps above and below [math]\displaystyle{ l_1 }[/math] respectively and that contain [math]\displaystyle{ O(\sqrt{n}) }[/math] vertices, respectively, for otherwise there would be more than [math]\displaystyle{ n }[/math] vertices in the levels near [math]\displaystyle{ l_1 }[/math]. They show that there must be a separator [math]\displaystyle{ S }[/math] formed by the union of [math]\displaystyle{ l_0 }[/math] and [math]\displaystyle{ l_2 }[/math], the endpoints of an edge [math]\displaystyle{ e }[/math] of [math]\displaystyle{ G }[/math] 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 [math]\displaystyle{ e }[/math] back up to level [math]\displaystyle{ l_0 }[/math]. The size of the separator [math]\displaystyle{ S }[/math] constructed in this way is at most [math]\displaystyle{ \sqrt{8n}\approx 2.83\sqrt{n} }[/math]. The vertices of the separator and the two disjoint subgraphs can be found in linear time.[4]

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 [math]\displaystyle{ A }[/math], [math]\displaystyle{ S }[/math], and [math]\displaystyle{ B }[/math] such that [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] each have at most [math]\displaystyle{ 2/3 }[/math] of the total cost and [math]\displaystyle{ S }[/math] has [math]\displaystyle{ O(\sqrt{n}) }[/math] vertices, with no edges from [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math].[4] By analysing a similar separator construction more carefully, (Djidjev 1982) shows that the bound on the size of [math]\displaystyle{ S }[/math] can be reduced to [math]\displaystyle{ \sqrt{6n}\approx 2.45\sqrt{n} }[/math].[2]

(Holzer Schulz) 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 [math]\displaystyle{ e }[/math] that is not part of the tree, they form a cycle by combining [math]\displaystyle{ e }[/math] 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.[5]

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 [math]\displaystyle{ 2n/3 }[/math] vertices. (Miller 1986) proves this (with a separator size of [math]\displaystyle{ \sqrt{8n} }[/math]) by using the Lipton–Tarjan technique for a modified version of breadth first search in which the levels of the search form simple cycles.[6]

(Alon Seymour) prove the existence of simple cycle separators more directly: let [math]\displaystyle{ C }[/math] be a cycle of at most [math]\displaystyle{ \sqrt{8n} }[/math] vertices, with at most [math]\displaystyle{ 2n/3 }[/math] vertices outside [math]\displaystyle{ C }[/math], that forms as even a partition of inside and outside as possible. They show that these assumptions force [math]\displaystyle{ C }[/math] to be a separator. For otherwise, the distances within [math]\displaystyle{ C }[/math] must equal the distances in the disk enclosed by [math]\displaystyle{ C }[/math] (a shorter path through the interior of the disk would form part of the boundary of a better cycle). Additionally, [math]\displaystyle{ C }[/math] must have length exactly [math]\displaystyle{ \sqrt{8n} }[/math], as otherwise it could be improved by replacing one of its edges by the other two sides of a triangle. If the vertices in [math]\displaystyle{ C }[/math] are numbered (in clockwise order) from [math]\displaystyle{ 1 }[/math] to [math]\displaystyle{ \sqrt{8n} }[/math], and vertex [math]\displaystyle{ i }[/math] is matched up with vertex [math]\displaystyle{ \sqrt{8n}-i+1 }[/math], 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 [math]\displaystyle{ n }[/math], a contradiction. With some additional work they show by a similar method that there exists a simple cycle separator of size at most [math]\displaystyle{ \sqrt{9n/2} \approx 2.12\sqrt{n} }[/math].[7]

(Djidjev Venkatesan) further improved the constant factor in the simple cycle separator theorem to [math]\displaystyle{ 1.97\sqrt{n} }[/math]. Their method can also find simple cycle separators for graphs with non-negative vertex weights, with separator size at most [math]\displaystyle{ 2\sqrt{n} }[/math], and can generate separators with smaller size at the expense of a more uneven partition of the graph.[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.[9]

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 (Miller Teng) show, for such a packing, there exists a circle that has at most [math]\displaystyle{ 3n/4 }[/math] disks touching or inside it, at most [math]\displaystyle{ 3n/4 }[/math] disks touching or outside it, and that crosses [math]\displaystyle{ O(\sqrt{n}) }[/math] disks.[10]

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 [math]\displaystyle{ 3n/4 }[/math] 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 [math]\displaystyle{ n }[/math] non-negative real numbers is bounded by a constant, the sum of the numbers themselves is [math]\displaystyle{ O(\sqrt{n}) }[/math]. Therefore, the expected number of disks crossed by a random plane is [math]\displaystyle{ O(\sqrt{n}) }[/math] 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 [math]\displaystyle{ O(\sqrt{n}) }[/math] 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 [math]\displaystyle{ 3n/4 }[/math] vertices in each of these two subsets.[11]

This method leads to a randomized algorithm that finds such a separator in linear time,[10] and a less-practical deterministic algorithm with the same linear time bound.[12] 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[13] [math]\displaystyle{ \sqrt{\frac{2\pi}{\sqrt 3}}\left(\frac{1+\sqrt 3}{2\sqrt2}+o(1)\right)\sqrt n\approx 1.84\sqrt n. }[/math] Although this improved separator size bound comes at the expense of a more-uneven partition of the graph, (Spielman Teng) argue that it provides an improved constant factor in the time bounds for nested dissection compared to the separators of (Alon Seymour). The size of the separators it produces can be further improved, in practice, by using a nonuniform distribution for the random cutting planes.[14]

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 [math]\displaystyle{ [1,2] }[/math]. 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.[15]

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.[16] As (Spielman Teng) 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 [math]\displaystyle{ O(1/\sqrt{n}) }[/math]. 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 [math]\displaystyle{ O(\sqrt{n}) }[/math] edges. The endpoints of these edges form a separator of size [math]\displaystyle{ O(\sqrt{n}) }[/math].[17]

Edge separators

A variation of the planar separator theorem involves edge separators, small sets of edges forming a cut between two subsets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] of the vertices of the graph. The two sets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] must each have size at most a constant fraction of the number [math]\displaystyle{ n }[/math] of vertices of the graph (conventionally, both sets have size at most [math]\displaystyle{ 2n/3 }[/math]), and each vertex of the graph belongs to exactly one of [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math]. The separator consists of the edges that have one endpoint in [math]\displaystyle{ A }[/math] and one endpoint in [math]\displaystyle{ B }[/math]. 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 [math]\displaystyle{ n-1 }[/math], 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 [math]\displaystyle{ \Delta }[/math] has an edge separator of size [math]\displaystyle{ O(\sqrt{\Delta n}) }[/math].[18]

A simple cycle separator in the dual graph of a planar graph forms an edge separator in the original graph.[19] Applying the simple cycle separator theorem of (Gazit Miller) to the dual graph of a given planar graph strengthens the [math]\displaystyle{ O(\sqrt{\Delta n}) }[/math] 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.

(Papadimitriou Sideri) describe a polynomial time algorithm for finding the smallest edge separator that partitions a graph [math]\displaystyle{ G }[/math] into two subgraphs of equal size, when [math]\displaystyle{ G }[/math] 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.

Lower bounds

A polyhedron formed by replacing each of the faces of an icosahedron by a mesh of 100 triangles, an example of the lower bound construction of (Djidjev 1982)

In a [math]\displaystyle{ \sqrt{n}\times\sqrt{n} }[/math] grid graph, a set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ s \lt \sqrt{n} }[/math] points can enclose a subset of at most [math]\displaystyle{ s(s-1)/2 }[/math] grid points, where the maximum is achieved by arranging [math]\displaystyle{ S }[/math] in a diagonal line near a corner of the grid. Therefore, in order to form a separator that separates at least [math]\displaystyle{ n/3 }[/math] of the points from the remaining grid, [math]\displaystyle{ s }[/math] needs to be at least [math]\displaystyle{ \sqrt{2n/3}\approx 0.82\sqrt{n} }[/math].

There exist [math]\displaystyle{ n }[/math]-vertex planar graphs (for arbitrarily large values of [math]\displaystyle{ n }[/math]) such that, for every separator [math]\displaystyle{ S }[/math] that partitions the remaining graph into subgraphs of at most [math]\displaystyle{ 2n/3 }[/math] vertices, [math]\displaystyle{ S }[/math] has at least [math]\displaystyle{ \sqrt{4\pi n/\sqrt{27}}\approx1.56\sqrt{n} }[/math].[2] 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 [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] 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 [math]\displaystyle{ O(\sqrt{n}) }[/math]. That is, a separator formed in this way has width [math]\displaystyle{ O(\sqrt{n}) }[/math], and can be used to show that every planar graph has treewidth [math]\displaystyle{ O(\sqrt{n}) }[/math].

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 [math]\displaystyle{ O(n\log n) }[/math] 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.[20]

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 [math]\displaystyle{ G_1 }[/math] and [math]\displaystyle{ G_2 }[/math] 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 [math]\displaystyle{ O(\sqrt{n}) }[/math] and any planar graph has branchwidth [math]\displaystyle{ O(\sqrt{n}) }[/math]. 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.[21]

By applying methods of (Alon Seymour) more directly in the construction of branch-decompositions, (Fomin Thilikos) show that every planar graph has branchwidth at most [math]\displaystyle{ 2.12\sqrt{n} }[/math], 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 [math]\displaystyle{ 3/2 }[/math] its branchwidth, this also shows that planar graphs have treewidth at most [math]\displaystyle{ 3.18\sqrt{n} }[/math].

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.[22]

Possibly the earliest known separator theorem is a result of (Jordan 1869) that any tree can be partitioned into subtrees of at most [math]\displaystyle{ n/2 }[/math] vertices each by the removal of a single vertex.[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. 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 [math]\displaystyle{ G }[/math] is not planar, but can be embedded on a surface of genus [math]\displaystyle{ g }[/math], then it has a separator with [math]\displaystyle{ O(\sqrt{gn}) }[/math] vertices. (Gilbert Hutchinson) prove this by using a similar approach to that of (Lipton Tarjan). 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 [math]\displaystyle{ g }[/math] also have edge separators of size [math]\displaystyle{ O(\sqrt{g\Delta n}) }[/math].[23]

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 [math]\displaystyle{ h }[/math] vertices, then it has a separator with [math]\displaystyle{ O(h\sqrt{n}) }[/math] vertices, and such a separator can be found in time [math]\displaystyle{ O(n^{1+\varepsilon}) }[/math] for any [math]\displaystyle{ \varepsilon \gt 0 }[/math].[24]

An intersection graph of disks, with at most [math]\displaystyle{ k=5 }[/math] disks covering any point of the plane

The circle separator method of (Miller Teng) generalizes to the intersection graphs of any system of [math]\displaystyle{ d }[/math]-dimensional balls with the property that any point in space is covered by at most some constant number [math]\displaystyle{ k }[/math] of balls, to [math]\displaystyle{ k }[/math]-nearest-neighbor graphs in [math]\displaystyle{ d }[/math] dimensions,[10] and to the graphs arising from finite element meshes.[25] The sphere separators constructed in this way partition the input graph into subgraphs of at most [math]\displaystyle{ n(d+1)/(d+2) }[/math] vertices. The size of the separators for [math]\displaystyle{ k }[/math]-ply ball intersection graphs and for [math]\displaystyle{ k }[/math]-nearest-neighbor graphs is [math]\displaystyle{ O(k^{1/d}n^{1-1/d}) }[/math].[10]

If a hereditary family of graphs has a separator theorem with separators of size [math]\displaystyle{ n^c }[/math], for some [math]\displaystyle{ c\lt 1 }[/math], 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.[26]

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:

  • Partition the given graph [math]\displaystyle{ G }[/math] into three subsets [math]\displaystyle{ S }[/math], [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math] according to the planar separator theorem
  • Recursively search for the shortest cycles in [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math]
  • Use Dijkstra's algorithm to find, for each vertex [math]\displaystyle{ s }[/math] in [math]\displaystyle{ S }[/math], the shortest cycle through [math]\displaystyle{ s }[/math] in [math]\displaystyle{ G }[/math].
  • Return the shortest of the cycles found by the above steps.

The time for the two recursive calls to [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] in this algorithm is dominated by the time to perform the [math]\displaystyle{ O(\sqrt{n}) }[/math] calls to Dijkstra's algorithm, so this algorithm finds the shortest cycle in [math]\displaystyle{ O(n^{3/2}\log n) }[/math] time.

A faster algorithm for the same shortest cycle problem, running in time [math]\displaystyle{ O(n\log^3 n) }[/math], was given by (Wulff-Nilsen 2009). 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 [math]\displaystyle{ S }[/math] belong to a single face of the graphs inside and outside the cycle separator. He then replaces the [math]\displaystyle{ O(\sqrt{n}) }[/math] 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 [math]\displaystyle{ O(n\log\log n) }[/math] time,[27] and the shortest cycle in an unweighted undirected planar graph (its girth) may be found in time [math]\displaystyle{ O(n) }[/math].[28] (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.[29] This is an improvement of Dijkstra's algorithm with iterative search on a carefully selected subset of the vertices. This version takes [math]\displaystyle{ O(n\sqrt{\log n}) }[/math] time in an [math]\displaystyle{ n }[/math]-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 [math]\displaystyle{ r }[/math]-division of an [math]\displaystyle{ n }[/math]-node graph that is a graph division into [math]\displaystyle{ O(n/r) }[/math] regions, each containing [math]\displaystyle{ O(r) }[/math] nodes including [math]\displaystyle{ O(\sqrt{r}) }[/math] boundary nodes. Frederickson showed that an [math]\displaystyle{ r }[/math]-division can be found in [math]\displaystyle{ O(n\log n) }[/math] time by recursive application of separator theorem.

The sketch of his algorithm to solve the problem is as follows.

  1. Preprocessing Phase: Partition the graph into carefully selected subsets of vertices and determine the shortest paths between all pairs of vertices in these subsets, where intermediate vertices on this path are not in the subset. This phase requires a planar graph [math]\displaystyle{ G_0 }[/math] to be transformed into [math]\displaystyle{ G }[/math] with no vertex having degree greater than three. From a corollary of Euler's formula, the number of vertices in the resulting graph will be [math]\displaystyle{ n\le 6n_0-12 }[/math], where [math]\displaystyle{ n_0 }[/math] is the number of vertices in [math]\displaystyle{ G_0 }[/math]. This phase also ensures the following properties of a suitable [math]\displaystyle{ r }[/math]-division. A suitable [math]\displaystyle{ r }[/math]-division of a planar graph is an [math]\displaystyle{ r }[/math]-division such that,
    • each boundary vertex is contained in at most three regions, and
    • any region that is not connected consists of connected components, all of which share boundary vertices with exactly the same set of either one or two connected regions.
  2. Search Phase:
    • Main Thrust: Find shortest distances from the source to each vertex in the subset. When a vertex [math]\displaystyle{ v }[/math] in the subset is closed, the tentative distance [math]\displaystyle{ d(w) }[/math] must be updated for all vertices [math]\displaystyle{ w }[/math] in the subset such that a path exists from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math].
    • Mop-up: Determine shortest distances to every remaining vertex.

Henzinger et al. extended Frederickson's [math]\displaystyle{ r }[/math]-division technique for the single source shortest path algorithm in planar graphs for nonnegative edge-lengths and proposed a linear time algorithm.[30] Their method generalizes Frederickson's notion of graph-divisions such that now an [math]\displaystyle{ (r,s) }[/math]-division of an [math]\displaystyle{ n }[/math]-node graph is a division into [math]\displaystyle{ O(n/r) }[/math] regions, each containing [math]\displaystyle{ r^{O(1)} }[/math] nodes, each having at most [math]\displaystyle{ s }[/math] boundary nodes. If an [math]\displaystyle{ (r,s) }[/math]-division is repeatedly divided into smaller regions, that is called a recursive division. This algorithm uses approximately [math]\displaystyle{ \log^* n }[/math] levels of divisions, where [math]\displaystyle{ \log^* }[/math] denotes the iterated logarithm function. The recursive division is represented by a rooted tree whose leaves are labeled by distinct edge of [math]\displaystyle{ G }[/math]. The root of the tree represents the region consisting of all of [math]\displaystyle{ G }[/math], 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.[31] The fill-in of this method (the number of nonzero coefficients of the resulting Cholesky decomposition of the matrix) is [math]\displaystyle{ O(n\log n) }[/math],[32] allowing this method to be competitive with iterative methods for the same problems.[31]

Klein, Mozes and Weimann[33] gave an [math]\displaystyle{ O(n\log^2 n) }[/math]-time, linear-space algorithm to find the shortest path distances from a source vertex [math]\displaystyle{ s }[/math] 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 [math]\displaystyle{ C }[/math] that passes through [math]\displaystyle{ O(\sqrt{n}) }[/math] nodes (and no arcs) such that between [math]\displaystyle{ n/3 }[/math] and [math]\displaystyle{ 2n/3 }[/math] nodes are enclosed by [math]\displaystyle{ C }[/math]. Nodes through which [math]\displaystyle{ C }[/math] passes are boundary nodes. The original graph [math]\displaystyle{ G }[/math] is separated into two subgraphs [math]\displaystyle{ G_0 }[/math] and [math]\displaystyle{ G_1 }[/math] by cutting the planar embedding along [math]\displaystyle{ C }[/math] and duplicating the boundary nodes. The boundary nodes in each graph [math]\displaystyle{ G_i }[/math] lie on the boundary of a single face [math]\displaystyle{ F_i }[/math].

The overview of their approach is given below.

  • Recursive call: The first stage recursively computes the distances from [math]\displaystyle{ r }[/math] within each graph [math]\displaystyle{ G_i }[/math].
  • Intra-part boundary-distances: For each graph [math]\displaystyle{ G_i }[/math] compute all distances in [math]\displaystyle{ G_i }[/math] between boundary nodes. This takes [math]\displaystyle{ O(n\log n) }[/math] time.
  • Single-source inter-part boundary distances: A shortest path in [math]\displaystyle{ G }[/math] passes back and forth between [math]\displaystyle{ G_0 }[/math] and [math]\displaystyle{ G_1 }[/math] to compute the distances in [math]\displaystyle{ G }[/math] from [math]\displaystyle{ r }[/math] to all the boundary nodes. Alternating iterations use the all-boundary-distances in [math]\displaystyle{ G_0 }[/math] and [math]\displaystyle{ G_1 }[/math]. The number of iterations is [math]\displaystyle{ O(\sqrt{n}) }[/math], and the overall time for this stage is [math]\displaystyle{ O(n\alpha(n)) }[/math] where [math]\displaystyle{ \alpha(n) }[/math] is the inverse Ackermann function.
  • Single-source inter-part distances: The distances computed in the previous stages are used, together with a Dijkstra computation within a modified version of each Gi , to compute the distances in [math]\displaystyle{ G }[/math] from [math]\displaystyle{ r }[/math] to all the nodes. This stage takes [math]\displaystyle{ O(n\log n) }[/math] time.
  • Rerooting single-source distances: The distances from [math]\displaystyle{ r }[/math] in [math]\displaystyle{ G }[/math] are transformed into nonnegative lengths, and again Dijkstra's algorithm is used to compute distances from [math]\displaystyle{ s }[/math]. This stage requires [math]\displaystyle{ O(n\log n) }[/math] time.

An important part of this algorithm is the use of price functions and reduced lengths. For a directed graph [math]\displaystyle{ G }[/math] with arc-lengths [math]\displaystyle{ \ell(uv) }[/math], a price function is a function [math]\displaystyle{ \varphi }[/math] from the nodes of [math]\displaystyle{ G }[/math] to the real numbers. For an arc [math]\displaystyle{ uv }[/math], the reduced length with respect to [math]\displaystyle{ \varphi }[/math] is [math]\displaystyle{ \ell_\varphi(uv) = \ell(uv) + \varphi(u) - \varphi(v) }[/math]. A feasible price function is a price function that induces nonnegative reduced lengths on all arcs of [math]\displaystyle{ G }[/math]. 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[34] and point location,[35] algorithms for polygon triangulation,[20] shortest paths,[36] and the construction of nearest neighbor graphs,[37] and approximation algorithms for the maximum independent set of a planar graph.[35]

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 [math]\displaystyle{ \sqrt{n} }[/math] or [math]\displaystyle{ \sqrt{n}\log n }[/math]. 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.[38] 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.[39]

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 [math]\displaystyle{ \sqrt{k} }[/math], where [math]\displaystyle{ k }[/math] is the parameter of the algorithm. For instance, time bounds of this form are known for finding vertex covers and dominating sets of size [math]\displaystyle{ k }[/math].[40]

Approximation algorithms

(Lipton Tarjan) 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 [math]\displaystyle{ O(n/\sqrt{\log n}) }[/math] the removal of which partitions the graph into subgraphs of size at most [math]\displaystyle{ c\log n }[/math], for any constant [math]\displaystyle{ c }[/math]. By the four-color theorem, there exists an independent set of size at least [math]\displaystyle{ n/4 }[/math], 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[20] 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 [math]\displaystyle{ 1-1/\sqrt{\log n} }[/math] of optimal, in linear time. However, for approximation ratios even closer to one than this factor, a later approach of (Baker 1994) (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.[41] (Arora Grigni) 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 [math]\displaystyle{ k }[/math] and repeatedly subdivide the given planar graph using separators into [math]\displaystyle{ O(n/k) }[/math] subgraphs of size at most [math]\displaystyle{ k }[/math], with [math]\displaystyle{ O(n/\sqrt{k}) }[/math] vertices in the separators. With an appropriate choice of [math]\displaystyle{ k }[/math] (at most proportional to the logarithm of [math]\displaystyle{ n }[/math]) the number of non-isomorphic [math]\displaystyle{ k }[/math]-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 [math]\displaystyle{ P_n }[/math] [math]\displaystyle{ n }[/math]-vertex graphs in the family of graphs to be represented, then an individual graph in the family can be represented using only [math]\displaystyle{ (1+o(1))\log_2 P_n }[/math] bits.[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.[43]

Universal graphs

A universal graph for a family [math]\displaystyle{ \mathcal{F} }[/math] of graphs is a graph that contains every member of [math]\displaystyle{ \mathcal{F} }[/math] as a subgraphs. Separators can be used to show that the [math]\displaystyle{ n }[/math]-vertex planar graphs have universal graphs with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ O(n^{3/2}) }[/math] edges.[44]

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 [math]\displaystyle{ c }[/math], the magnitude of which at most a constant times [math]\displaystyle{ \sqrt{n} }[/math], such that the vertices of every [math]\displaystyle{ n }[/math]-vertex planar graph can be separated into subsets [math]\displaystyle{ A }[/math], [math]\displaystyle{ S }[/math], and [math]\displaystyle{ B }[/math], with no edges from [math]\displaystyle{ A }[/math] to [math]\displaystyle{ B }[/math], with [math]\displaystyle{ |S|=c }[/math], and with [math]\displaystyle{ |A|=|B|=(n-c)/2 }[/math]. 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 [math]\displaystyle{ n/2 }[/math] 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 [math]\displaystyle{ n }[/math]-vertex planar graphs that again does not depend on the graph structure: the tree-decomposition formed from this hierarchy has width [math]\displaystyle{ O(\sqrt{n}) }[/math] 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 [math]\displaystyle{ O(n^{3/2}) }[/math] vertices that contains every [math]\displaystyle{ n }[/math]-vertex planar graph as a subgraph. A similar construction shows that bounded-degree planar graphs have universal graphs with [math]\displaystyle{ O(n\log n) }[/math] 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 [math]\displaystyle{ \Omega(n\log n) }[/math] edges.[44]

(Esperet Joret) announced that the [math]\displaystyle{ O(n^{3/2}) }[/math] construction using separators can be improved, to [math]\displaystyle{ n^{1+o(1)} }[/math].

See also

Notes

  1. ↑ Alon, Seymour & Thomas (1990).
  2. ↑ 2.0 2.1 2.2 Djidjev (1982).
  3. ↑ (George 1973). Instead of using a row or column of a grid graph, George partitions the graph into four pieces by using the union of a row and a column as a separator.
  4. ↑ 4.0 4.1 Lipton & Tarjan (1979).
  5. ↑ Holzer et al. (2009).
  6. ↑ Miller (1986).
  7. ↑ Alon, Seymour & Thomas (1994).
  8. ↑ Djidjev & Venkatesan (1997).
  9. ↑ Gazit & Miller (1990).
  10. ↑ 10.0 10.1 10.2 10.3 10.4 Miller et al. (1997).
  11. ↑ (Miller Teng); (Pach Agarwal)
  12. ↑ Eppstein, Miller & Teng (1995).
  13. ↑ Spielman & Teng (1996).
  14. ↑ Gremban, Miller & Teng (1997).
  15. ↑ Har-Peled (2011).
  16. ↑ (Donath Hoffman); (Fiedler 1973).
  17. ↑ Spielman & Teng (2007).
  18. ↑ (Miller 1986) proved this result for 2-connected planar graphs, and (Diks Djidjev) extended it to all planar graphs.
  19. ↑ (Miller 1986); (Gazit Miller).
  20. ↑ 20.0 20.1 20.2 Goodrich (1995).
  21. ↑ Seymour & Thomas (1994).
  22. ↑ (Lipton Tarjan); (Erdős Graham).
  23. ↑ Sýkora & Vrt'o (1993).
  24. ↑ (Kawarabayashi Reed). For earlier work on separators in minor-closed families see (Alon Seymour), (Plotkin Rao), and (Reed Wood).
  25. ↑ Miller et al. (1998).
  26. ↑ Dvořák & Norin (2016).
  27. ↑ Łącki & Sankowski (2011).
  28. ↑ Chang & Lu (2011).
  29. ↑ Frederickson (1987).
  30. ↑ Henzinger et al. (1997).
  31. ↑ 31.0 31.1 George (1973).
  32. ↑ (Lipton Rose); (Gilbert Tarjan).
  33. ↑ Klein, Mozes & Weimann (2010).
  34. ↑ (Eppstein Galil); (Eppstein Galil).
  35. ↑ 35.0 35.1 Lipton & Tarjan (1980).
  36. ↑ (Klein Rao); (Tazari Müller-Hannemann).
  37. ↑ Frieze, Miller & Teng (1992).
  38. ↑ (Bern 1990); (Deĭneko Klinz); (Dorn Penninkx); (Lipton Tarjan).
  39. ↑ Smith & Wormald (1998).
  40. ↑ (Alber Fernau); (Fomin Thilikos).
  41. ↑ (Bar-Yehuda Even); (Chiba Nishizeki).
  42. ↑ He, Kao & Lu (2000).
  43. ↑ (Blandford Blelloch); (Blelloch Farzan).
  44. ↑ 44.0 44.1 (Babai Chung); (Bhatt Chung); (Chung 1990).

References



Retrieved from "https://handwiki.org/wiki/index.php?title=Planar_separator_theorem&oldid=3720191"