In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the planar separator theorem is a form of
isoperimetric inequality
In mathematics, the isoperimetric inequality is a geometric inequality involving the perimeter of a set and its volume. In n-dimensional space \R^n the inequality lower bounds the surface area or perimeter \operatorname(S) of a set S\subset\R^n ...
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
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
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 , 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 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
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
Tree decompositions are also called junction trees ...
or a
branch-decomposition of the graph. Separator hierarchies may be used to devise efficient
divide and conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved direc ...
s for planar graphs, and
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
on these hierarchies can be used to devise
exponential time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
and
fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
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
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three equations in th ...
arising from
finite element method
The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat ...
s.
Beyond planar graphs, separator theorems have been applied to other classes of graphs including
graphs excluding a fixed minor,
nearest neighbor graph
The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from ''p'' to ''q'' whenever ''q'' is a nea ...
s, 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
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
and
polynomial expansion
In mathematics, an expansion of a product of sums expresses it as a sum of products by using the fact that multiplication distributes over addition. Expansion of a polynomial expression can be obtained by repeatedly replacing subexpressions tha ...
.
Statement of the theorem
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
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
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. 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.
Example
Consider a
grid graph
In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a latti ...
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
.
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.
Constructions
Breadth-first layering
augment the given planar graph by additional edges, if necessary, so that it becomes maximal planar (every face in a planar embedding is a triangle). They then perform a
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...
, 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.
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
. By analysing a similar separator construction more carefully, shows that the bound on the size of
can be reduced to
.
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.
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
vertices. 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.
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
In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of Vertex (graph theory), vertices.
Pro ...
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
.
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. 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.
Circle separators
According to the
Koebe–Andreev–Thurston circle-packing theorem, any planar graph may be represented by a packing of circular disks in the plane with disjoint interiors, such that two vertices in the graph are adjacent if and only if the corresponding pair of disks are mutually tangent. As show, for such a packing, there exists a circle that has at most
disks touching or inside it, at most
disks touching or outside it, and that crosses
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
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.
This method leads to a
randomized algorithm that finds such a separator in
linear time, and a less-practical
deterministic algorithm
In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far ...
with the same linear time bound. By analyzing this algorithm carefully using known bounds on the
packing density
A packing density or packing fraction of a packing in some space is the fraction of the space filled by the figures making up the packing. In simplest terms, this is the ratio of the volume of bodies in a space to the volume of the space itself. I ...
of
circle packing
In geometry, circle packing is the study of the arrangement of circles (of equal or varying sizes) on a given surface such that no overlapping occurs and so that no circle can be enlarged without creating an overlap. The associated '' packing de ...
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.
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