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 ) {\displaystyle 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 2 n / 3 {\displaystyle 2n/3} 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 O ( n ) {\displaystyle 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 2 n / 3 {\displaystyle 2n/3} vertices.
Source: Wikipedia "Planar separator theorem" · CC BY-SA 4.0
Share this article: X · Bluesky