Planar separator theorem

  (Redirected from Planar Separator Theorem)

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an -vertex graph (where the invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most vertices.

A weaker form of the separator theorem with vertices in the separator instead of was originally proven by Ungar (1951), and the form with the tight asymptotic bound on the separator size was first proven by Lipton & Tarjan (1979). Since their work, the separator theorem has been reproven in several different ways, the constant in the term of the theorem has been improved, and it has been extended to certain classes of nonplanar graphs.

Repeated application of the separator theorem produces a separator hierarchy which may take the form of either a tree decomposition or a branch-decomposition of the graph. Separator hierarchies may be used to devise efficient divide and conquer algorithms for planar graphs, and dynamic programming on these hierarchies can be used to devise exponential time and fixed-parameter tractable algorithms for solving NP-hard optimization problems on these graphs. Separator hierarchies may also be used in nested dissection, an efficient variant of Gaussian elimination for solving sparse systems of linear equations arising from finite element methods.

Beyond planar graphs, separator theorems have been applied to other classes of graphs including graphs excluding a fixed minor, nearest neighbor graphs, and finite element meshes. The existence of a separator theorem for a class of graphs can be formalized and quantified by the concepts of treewidth and polynomial expansion.

Statement of the theoremEdit

As it is usually stated, the separator theorem states that, in any  -vertex planar graph  , there exists a partition of the vertices of   into three sets  ,  , and  , such that each of   and   has at most   vertices,   has   vertices, and there are no edges with one endpoint in   and one endpoint in  . It is not required that   or   form connected subgraphs of  .   is called the separator for this partition.

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

The constant   in the statement of the separator theorem is arbitrary and may be replaced by any other number in the open interval   without changing the form of the theorem: a partition into more equal subsets may be obtained from a less-even partition by repeatedly splitting the larger sets in the uneven partition and regrouping the resulting connected components.[2]

ExampleEdit

 
A planar separator for a grid graph

Consider a grid graph with   rows and   columns; the number   of vertices equals  . For instance, in the illustration,  ,  , and  . If   is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if   is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing   to be any of these central rows or columns, and removing   from the graph, partitions the graph into two smaller connected subgraphs   and  , each of which has at most   vertices. If   (as in the illustration), then choosing a central column will give a separator   with   vertices, and similarly if   then choosing a central row will give a separator with at most   vertices. Thus, every grid graph has a separator   of size at most  , the removal of which partitions it into two connected components, each of size at most  .[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   but may be larger than  , the bound on the size of the two subsets   and   (in the most common versions of the theorem) is   rather than  , and the two subsets   and   need not themselves form connected subgraphs.

ConstructionsEdit

Breadth-first layeringEdit

Lipton & Tarjan (1979) augment the given planar graph by additional edges, if necessary, so that it becomes maximal planar (every face in a planar embedding is a triangle). They then perform a breadth-first search, rooted at an arbitrary vertex  , and partition the vertices into levels by their distance from  . If   is the median level (the level such that the numbers of vertices at higher and lower levels are both at most  ) then there must be levels   and   that are   steps above and below   respectively and that contain   vertices, respectively, for otherwise there would be more than   vertices in the levels near  . They show that there must be a separator   formed by the union of   and  , the endpoints of an edge   of   that does not belong to the breadth-first search tree and that lies between the two levels, and the vertices on the two breadth-first search tree paths from the endpoints of   back up to level  . The size of the separator   constructed in this way is at most  . The vertices of the separator and the two disjoint subgraphs can be found in linear time.[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  ,  , and   such that   and   each have at most   of the total cost and   has   vertices, with no edges from   and  .[4] By analysing a similar separator construction more carefully, Djidjev (1982) shows that the bound on the size of   can be reduced to  .[2]

Holzer et al. (2009) suggest a simplified version of this approach: they augment the graph to be maximal planar and construct a breadth first search tree as before. Then, for each edge   that is not part of the tree, they form a cycle by combining   with the tree path that connects its endpoints. They then use as a separator the vertices of one of these cycles. Although this approach cannot be guaranteed to find a small separator for planar graphs of high diameter, their experiments indicate that it outperforms the Lipton–Tarjan and Djidjev breadth-first layering methods on many types of planar graph.[5]

Simple cycle separatorsEdit

For a graph that is already maximal planar it is possible to show a stronger construction of a simple cycle separator, a cycle of small length such that the inside and the outside of the cycle (in the unique planar embedding of the graph) each have at most   vertices. Miller (1986) proves this (with a separator size of  ) by using the Lipton–Tarjan technique for a modified version of breadth first search in which the levels of the search form simple cycles.[6]

Alon, Seymour & Thomas (1994) prove the existence of simple cycle separators more directly: they let   be a cycle of at most   vertices, with at most   vertices outside  , that forms as even a partition of inside and outside as possible, and they show that these assumptions force   to be a separator. For otherwise, the distances within   must equal the distances in the disk enclosed by   (a shorter path through the interior of the disk would form part of the boundary of a better cycle). Additionally,   must have length exactly  , as otherwise it could be improved by replacing one of its edges by the other two sides of a triangle. If the vertices in   are numbered (in clockwise order) from   to  , and vertex   is matched up with vertex  , then these matched pairs can be connected by vertex-disjoint paths within the disk, by a form of Menger's theorem for planar graphs. However, the total length of these paths would necessarily exceed  , a contradiction. With some additional work they show by a similar method that there exists a simple cycle separator of size at most  .[7]

Djidjev & Venkatesan (1997) further improved the constant factor in the simple cycle separator theorem to  . Their method can also find simple cycle separators for graphs with non-negative vertex weights, with separator size at most  , and can generate separators with smaller size at the expense of a more uneven partition of the graph.[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 separatorsEdit

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 et al. (1997) show, for such a packing, there exists a circle that has at most   disks touching or inside it, at most   disks touching or outside it, and that crosses   disks.[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   of the disks. If a plane through the center is chosen uniformly at random, a disk will be crossed with probability proportional to its radius. Therefore, the expected number of disks that are crossed is proportional to the sum of the radii of the disks. However, the sum of the squares of the radii is proportional to the total area of the disks, which is at most the total surface area of the unit sphere, a constant. An argument involving Jensen's inequality shows that, when the sum of squares of   non-negative real numbers is bounded by a constant, the sum of the numbers themselves is  . Therefore, the expected number of disks crossed by a random plane is   and there exists a plane that crosses at most that many disks. This plane intersects the sphere in a great circle, which projects back down to a circle in the plane with the desired properties. The   disks crossed by this circle correspond to the vertices of a planar graph separator that separates the vertices whose disks are inside the circle from the vertices whose disks are outside the circle, with at most   vertices in each of these two subsets.[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]

 
Although this improved separator size bound comes at the expense of a more-uneven partition of the graph, Spielman & Teng (1996) argue that it provides an improved constant factor in the time bounds for nested dissection compared to the separators of Alon, Seymour & Thomas (1990). The size of the separators it produces can be further improved, in practice, by using a nonuniform distribution for the random cutting planes.[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  . 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 partitioningEdit

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 (2007) 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  . 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   edges. The endpoints of these edges form a separator of size  .[17]

Edge separatorsEdit

A variation of the planar separator theorem involves edge separators, small sets of edges forming a cut between two subsets   and   of the vertices of the graph. The two sets   and   must each have size at most a constant fraction of the number   of vertices of the graph (conventionally, both sets have size at most  ), and each vertex of the graph belongs to exactly one of   and  . The separator consists of the edges that have one endpoint in   and one endpoint in  . 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  , 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   has an edge separator of size  .[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 (1990) to the dual graph of a given planar graph strengthens the   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 (1996) describe a polynomial time algorithm for finding the smallest edge separator that partitions a graph   into two subgraphs of equal size, when   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 boundsEdit

 
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   grid graph, a set   of   points can enclose a subset of at most   grid points, where the maximum is achieved by arranging   in a diagonal line near a corner of the grid. Therefore, in order to form a separator that separates at least   of the points from the remaining grid,   needs to be at least  .

There exist  -vertex planar graphs (for arbitrarily large values of  ) such that, for every separator   that partitions the remaining graph into subgraphs of at most   vertices,   has at least  .[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 hierarchiesEdit

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   and   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  . That is, a separator formed in this way has width  , and can be used to show that every planar graph has treewidth  .

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   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   and   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   and any planar graph has branchwidth  . 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 & Thomas (1994) more directly in the construction of branch-decompositions, Fomin & Thilikos (2006a) show that every planar graph has branchwidth at most  , 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   its branchwidth, this also shows that planar graphs have treewidth at most  .

Other classes of graphsEdit

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   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   is not planar, but can be embedded on a surface of genus  , then it has a separator with   vertices. Gilbert, Hutchinson & Tarjan (1984) prove this by using a similar approach to that of Lipton & Tarjan (1979). 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   also have edge separators of size  .[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   vertices, then it has a separator with   vertices, and such a separator can be found in time   for any  .[24]

 
An intersection graph of disks, with at most   disks covering any point of the plane

The circle separator method of Miller et al. (1997) generalizes to the intersection graphs of any system of  -dimensional balls with the property that any point in space is covered by at most some constant number   of balls, to  -nearest-neighbor graphs in   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   vertices. The size of the separators for  -ply ball intersection graphs and for  -nearest-neighbor graphs is  .[10]

If a hereditary family of graphs has a separator theorem with separators of size  , for some  , 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]

ApplicationsEdit

Divide and conquer algorithmsEdit

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   into three subsets  ,  ,   according to the planar separator theorem
  • Recursively search for the shortest cycles in   and  
  • Use Dijkstra's algorithm to find, for each vertex   in  , the shortest cycle through   in  .
  • Return the shortest of the cycles found by the above steps.

The time for the two recursive calls to   and   in this algorithm is dominated by the time to perform the   calls to Dijkstra's algorithm, so this algorithm finds the shortest cycle in   time.

A faster algorithm for the same shortest cycle problem, running in time  , 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   belong to a single face of the graphs inside and outside the cycle separator. He then replaces the   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   time,[27] and the shortest cycle in an unweighted undirected planar graph (its girth) may be found in time  .[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   time in an  -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  -division of an  -node graph that is a graph division into   regions, each containing   nodes including   boundary nodes. Frederickson showed that an  -division can be found in   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   to be transformed into   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  , where   is the number of vertices in  . This phase also ensures the following properties of a suitable  -division. A suitable  -division of a planar graph is an  -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   in the subset is closed, the tentative distance   must be updated for all vertices   in the subset such that a path exists from   to  .
    • Mop-up: Determine shortest distances to every remaining vertex.

Henzinger et al. extended Frederickson's  -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  -division of an  -node graph is a division into   regions, each containing   nodes, each having at most   boundary nodes. If an  -division is repeatedly divided into smaller regions, that is called a recursive division. This algorithm uses approximately   levels of divisions, where   denotes the iterated logarithm function. The recursive division is represented by a rooted tree whose leaves are labeled by distinct edge of  . The root of the tree represents the region consisting of all of  , 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  ,[32] allowing this method to be competitive with iterative methods for the same problems.[31]

Klein, Mozes and Weimann[33] gave an  -time, linear-space algorithm to find the shortest path distances from a source vertex   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   that passes through   nodes (and no arcs) such that between   and   nodes are enclosed by  . Nodes through which   passes are boundary nodes. The original graph   is separated into two subgraphs   and   by cutting the planar embedding along   and duplicating the boundary nodes. The boundary nodes in each graph   lie on the boundary of a single face  .

The overview of their approach is given below.

  • Recursive call: The first stage recursively computes the distances from   within each graph  .
  • Intra-part boundary-distances: For each graph   compute all distances in   between boundary nodes. This takes   time.
  • Single-source inter-part boundary distances: A shortest path in   passes back and forth between   and   to compute the distances in   from   to all the boundary nodes. Alternating iterations use the all-boundary-distances in   and  . The number of iterations is  , and the overall time for this stage is   where   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   from   to all the nodes. This stage takes   time.
  • Rerooting single-source distances: The distances from   in   are transformed into nonnegative lengths, and again Dijkstra's algorithm is used to compute distances from  . This stage requires   time.

An important part of this algorithm is the use of price functions and reduced lengths. For a directed graph   with arc-lengths  , a price function is a function   from the nodes of   to the real numbers. For an arc  , the reduced length with respect to   is  . A feasible price function is a price function that induces nonnegative reduced lengths on all arcs of  . 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 problemsEdit

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   or  . 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  , where   is the parameter of the algorithm. For instance, time bounds of this form are known for finding vertex covers and dominating sets of size  .[40]

Approximation algorithmsEdit

Lipton & Tarjan (1980) observed that the separator theorem may be used to obtain polynomial time approximation schemes for NP-hard optimization problems on planar graphs such as finding the maximum independent set. Specifically, by truncating a separator hierarchy at an appropriate level, one may find a separator of size   the removal of which partitions the graph into subgraphs of size at most  , for any constant  . By the four-color theorem, there exists an independent set of size at least  , 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   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 et al. (1998) use separators in a different way to approximate the travelling salesman problem for the shortest path metric on weighted planar graphs; their algorithm uses dynamic programming to find the shortest tour that, at each level of a separator hierarchy, crosses the separator a bounded number of times, and they show that as the crossing bound increases the tours constructed in this way have lengths that approximate the optimal tour.

Graph compressionEdit

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   and repeatedly subdivide the given planar graph using separators into   subgraphs of size at most  , with   vertices in the separators. With an appropriate choice of   (at most proportional to the logarithm of  ) the number of non-isomorphic  -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    -vertex graphs in the family of graphs to be represented, then an individual graph in the family can be represented using only   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 graphsEdit

A universal graph for a family   of graphs is a graph that contains every member of   as a subgraphs. Separators can be used to show that the  -vertex planar graphs have universal graphs with   vertices and   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  , the magnitude of which at most a constant times  , such that the vertices of every  -vertex planar graph can be separated into subsets  ,  , and  , with no edges from   to  , with  , and with  . 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   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  -vertex planar graphs that again does not depend on the graph structure: the tree-decomposition formed from this hierarchy has width   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   vertices that contains every  -vertex planar graph as a subgraph. A similar construction shows that bounded-degree planar graphs have universal graphs with   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   edges.[44]

Esperet, Joret & Morin (2020) announced that the   construction using separators can be improved, to  .

See alsoEdit

NotesEdit

  1. ^ Alon, Seymour & Thomas (1990).
  2. ^ a b c 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. ^ a b 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. ^ a b c d e Miller et al. (1997).
  11. ^ Miller et al. (1997); Pach & Agarwal (1995)
  12. ^ Eppstein, Miller & Teng (1995).
  13. ^ Spielman & Teng (1996).
  14. ^ Gremban, Miller & Teng (1997).
  15. ^ Har-Peled (2011).
  16. ^ Donath & Hoffman (1972); Fiedler (1973).
  17. ^ Spielman & Teng (2007).
  18. ^ Miller (1986) proved this result for 2-connected planar graphs, and Diks et al. (1993) extended it to all planar graphs.
  19. ^ Miller (1986); Gazit & Miller (1990).
  20. ^ a b c Goodrich (1995).
  21. ^ Seymour & Thomas (1994).
  22. ^ Lipton & Tarjan (1979); Erdős, Graham & Szemerédi (1976).
  23. ^ Sýkora & Vrt'o (1993).
  24. ^ Kawarabayashi & Reed (2010). For earlier work on separators in minor-closed families see Alon, Seymour & Thomas (1990), Plotkin, Rao & Smith (1994), and Reed & Wood (2009).
  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. ^ a b George (1973).
  32. ^ Lipton, Rose & Tarjan (1979); Gilbert & Tarjan (1986).
  33. ^ Klein, Mozes & Weimann (2010).
  34. ^ Eppstein et al. (1996); Eppstein et al. (1998).
  35. ^ a b Lipton & Tarjan (1980).
  36. ^ Klein et al. (1994); Tazari & Müller-Hannemann (2009).
  37. ^ Frieze, Miller & Teng (1992).
  38. ^ Bern (1990); Deĭneko, Klinz & Woeginger (2006); Dorn et al. (2005); Lipton & Tarjan (1980).
  39. ^ Smith & Wormald (1998).
  40. ^ Alber, Fernau & Niedermeier (2003); Fomin & Thilikos (2006b).
  41. ^ Bar-Yehuda & Even (1982); Chiba, Nishizeki & Saito (1981).
  42. ^ He, Kao & Lu (2000).
  43. ^ Blandford, Blelloch & Kash (2003); Blelloch & Farzan (2010).
  44. ^ a b Babai et al. (1982); Bhatt et al. (1989); Chung (1990).

ReferencesEdit