← All problems

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 ⁠ O(n)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/32n/3 ⁠ vertices. A weaker form of the separator theorem with ⁠ O(nlog⁡3/2n)O({\sqrt {n}}\log ^{3/2}n) ⁠ vertices in the separator instead of ⁠ O(n)O({\sqrt {n}}) ⁠ 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 ⁠ O(n)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.

References
  1. Wikipedia, Planar separator theorem, the article this theorem comes from.

Source: Wikipedia

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.