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 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 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.
and 25 Related for: Planar separator theorem information
In graph theory, the planarseparatortheorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into...
known as diaphragm Planarseparatortheorem, a theorem in graph theory Vertex separator, a notion in graph theory Geometric separator, a line that separates...
a theorem) states that every planar graph can be represented as an intersection graph of line segments in the plane. The planarseparatortheorem states...
for applications in computer science, such as the planarseparatortheorem. Let S be an (a,b)-separator, that is, a vertex subset that separates two nonadjacent...
excluded shallow minors can be partitioned analogously to the planarseparatortheorem for planar graphs. In particular, if the complete graph Kh is not a...
88: 141–164. Lipton, Richard J.; Tarjan, Robert E. (1979), "A separatortheorem for planar graphs", SIAM Journal on Applied Mathematics, 36 (2): 177–189...
logically equivalent "past → future" form. Planarseparatortheorem (graph theory) states that any planar graph can be split into smaller pieces by removing...
resulting matrix has O(n log n) nonzeros, due to the planarseparatortheorem guaranteeing separators of size O(√n). For arbitrary graphs there is a nested...
Prize winner, 2014 SL (complexity) Take-grant protection model Planarseparatortheorem Richard Lipton at the Mathematics Genealogy Project Lipton, R (1975)...
the planarseparatortheorem can be used to show that n-vertex planar graphs have universal graphs with O(n3/2) edges, and that bounded-degree planar graphs...
Tarjan, Applications of a PlanarSeparatorTheorem, SIAM J. Comput. 1980 Noga Alon, Paul Seymour, Robin Thomas, A SeparatorTheorem for Graphs with an Excluded...
Personal Storage Table, a file format used in Microsoft applications Planarseparatortheorem, in graph theory Pocket set theory, in mathematics Post-stall technology...
Isoperimetric dimension Isoperimetric point List of triangle inequalities Planarseparatortheorem Mixed volume Chaplygin problem: isoperimetric problem is a zero...
finite approximation factor unless P = NP. The planarseparatortheorem states that any n-vertex planar graph can be partitioned into roughly equal parts...
Additionally, the H-minor-free graphs have a separatortheorem similar to the planarseparatortheorem for planar graphs: for any fixed H, and any n-vertex...
proof that such separators can always be found is related to the PlanarSeparatorTheorem of Lipton and Tarjan, and these separators can be located in...
subgraph if it is not. Planarity testing algorithms typically take advantage of theorems in graph theory that characterize the set of planar graphs in terms...
rectangles. Ravi, S. S.; Hunt, H. B. (1987). "An application of the planarseparatortheorem to counting problems". Information Processing Letters. 25 (5):...
performed efficiently on them. The planar graphs do not have bounded treewidth, because the n × n grid graph is a planar graph with treewidth exactly n....
sublinear separatortheorems. Because of the connection between separators and expansion, every minor-closed graph family, including the family of planar graphs...
S2CID 6390600. Lipton, R. J.; Tarjan, R. E. (1980), "Applications of a planarseparatortheorem", SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046...
Hutchinson (born 1945), American graph theorist who extended the planarseparatortheorem to graphs of higher genus Marie Hušková (born 1942), Czech mathematician...
Because graphs of book thickness two are planar graphs, they obey the planarseparatortheorem: they have separators, subsets of vertices whose removal splits...
Global Information
