A graph separator is a set of vertices whose deletion separates a graph into smaller connected
components. A balanced separator of an 
-vertex graph is a set
whose deletion leaves no connected component
with more than 
vertices. For a string graph
with 
edges, a balanced separator of size 
can be found in polynomial
time (Davies et al. 2026). Davies et al. (2026) state that the
main-body mathematics was developed without AI assistance, while AI tools assisted
with Lean formalization.
Graph Separator
See also
Connected Component, String Graph, Vertex CutExplore with Wolfram|Alpha
References
Davies, J.; Rzążewski, P.; Spalding-Jamieson, J.; and Walczak, B. "Revisiting Separators in String Graphs, Region Intersection Graphs, and Induced-Minor-Free Graphs." 16 Oct 2026. https://arxiv.org/abs/2610.23792.Cite this as:
Weisstein, Eric W. "Graph Separator." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphSeparator.html