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) 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/3 vertices.
known for
Wikipage redirect
primaryTopic
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) 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/3 vertices.
has abstract
In graph theory, the planar se ...... raphs excluding a fixed minor.
@en
thumbnail
Link from a Wikipage to an external page
Wikipage page ID
18,978,005
Wikipage revision ID
734,818,018
hypernym
comment
In graph theory, the planar se ...... ich has at most 2n/3 vertices.
@en
label
Planar separator theorem
@en