Lipton–Tarjan separator theorem
E583430
The Lipton–Tarjan separator theorem is a fundamental result in graph theory that shows any planar graph can be efficiently divided into roughly equal parts by removing only a relatively small set of vertices, enabling faster algorithms for many computational problems.
Statements (44)
| Predicate | Object |
|---|---|
| instanceOf |
separator theorem
ⓘ
theorem in graph theory ⓘ |
| algorithmicAspect | separator can be found in linear time for planar graphs ⓘ |
| appliesTo | planar graphs ⓘ |
| assumption | graph is planar ⓘ |
| balanceProperty | separator splits the graph into roughly equal-sized parts ⓘ |
| citedAs | Lipton–Tarjan planar separator theorem NERFINISHED ⓘ |
| complexityImpact |
enables faster algorithms for many NP-hard problems on planar graphs
ⓘ
reduces running time of many planar graph algorithms from O(n^2) to near-linear or n^{3/2} ⓘ |
| componentSizeBound |
at most 2n/3 vertices per component
ⓘ
each component has at most 2n/3 vertices when separator is removed ⓘ |
| enables | divide-and-conquer algorithms on planar graphs ⓘ |
| field | graph theory ⓘ |
| generalizedBy | separator theorems for minor-closed graph classes ⓘ |
| graphClass |
simple planar graphs
ⓘ
undirected graphs ⓘ |
| influenceOn |
graph algorithms textbooks
ⓘ
parameterized complexity on planar graphs ⓘ |
| inspired | subsequent separator theorems in geometric graphs ⓘ |
| mainClaim |
every n-vertex planar graph has a vertex separator of size O(sqrt(n))
ⓘ
the removal of the separator partitions the planar graph into components each with at most a constant fraction of the vertices ⓘ |
| namedAfter |
Richard J. Lipton
NERFINISHED
ⓘ
Robert Endre Tarjan NERFINISHED ⓘ |
| originalAuthors |
Richard J. Lipton
NERFINISHED
ⓘ
Robert Endre Tarjan NERFINISHED ⓘ |
| originalTitle | A separator theorem for planar graphs NERFINISHED ⓘ |
| proofTechnique |
breadth-first search layering
ⓘ
cycle separators ⓘ planar embedding arguments ⓘ |
| publishedIn | Journal of the ACM NERFINISHED ⓘ |
| relatedConcept |
branchwidth
ⓘ
graph separator ⓘ minor-closed graph families ⓘ planar separator theorem NERFINISHED ⓘ treewidth ⓘ |
| separatorSizeBound | O(sqrt(n)) ⓘ |
| separatorType | vertex separator ⓘ |
| usedFor |
design of subquadratic algorithms on planar graphs
ⓘ
planar graph divide-and-conquer dynamic programming ⓘ planar graph maximum independent set approximation ⓘ planar graph recognition algorithms ⓘ planar graph shortest path algorithms ⓘ planar graph vertex cover algorithms ⓘ |
| yearProved | 1979 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.