The planar separator theorem, in graph theory, is a form of isoperimetric inequality for planar graphs stating that any planar graph on n vertices can be split into smaller pieces by removing a small number of vertices. Removing O(square root of n) vertices can partition the graph into disjoint pieces each with at most two thirds of the vertices; a weaker bound was proved by Ungar in 1951, and Lipton and Tarjan proved the tight bound in 1979, a result since used to build separator hierarchies for divide-and-conquer algorithms, dynamic programming on NP-hard problems, and nested dissection methods for sparse linear systems. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Planar separator theorem (Wikipedia)
Sources
1. Planar separator theorem (Wikipedia)
In Branch: Graph Theory, Lead sentenceQuote, In Branch: Graph Theory, Lead sentence
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.