Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Planar separator theorem
Summary
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 O(\sqrt{n}) vertices from an n-vertex graph (where the O invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most 2n/3 vertices.
A weaker form of the separator theorem with O(\sqrt{n}\log^{3/2}n) vertices in the separator instead of O(\sqrt{n}) was originally proven by , and the form with the tight asymptotic bound on the separator size was first proven by . Since their work, the separator theorem has been reproven in several different ways, the constant in the O(\sqrt n) term of the theorem has been improved, and it has been extended to certain classes of nonplanar graphs.
Repeated application of the separator theorem produces a separator hierarchy which may take the form of either a tree decomposition or a branch-decomposition of the graph. Separator hierarchies may be used to devise efficient divide and conquer 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.
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 .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.