Lower Bounds
In a √n × √n grid graph, a set S of s < √n points can enclose a subset of at most s(s − 1)/2 grid points, where the maximum is achieved by arranging S in a diagonal line near a corner of the grid. Therefore, in order to form a separator that separates at least n/3 of the points from the remaining grid, s needs to be at least √(2n/3), approximately 0.82√n.
There exist n-vertex planar graphs (for arbitrarily large values of n) such that, for every separator S that partitions the remaining graph into subgraphs of at most 2n/3 vertices, S has at least √(4π√3)√n vertices, approximately 1.56√n. The construction involves approximating a sphere by a convex polyhedron, replacing each of the faces of the polyhedron by a triangular mesh, and applying isoperimetric theorems for the surface of the sphere.
Read more about this topic: Planar Separator Theorem
Famous quotes containing the word bounds:
“How far men go for the material of their houses! The inhabitants of the most civilized cities, in all ages, send into far, primitive forests, beyond the bounds of their civilization, where the moose and bear and savage dwell, for their pine boards for ordinary use. And, on the other hand, the savage soon receives from cities iron arrow-points, hatchets, and guns, to point his savageness with.”
—Henry David Thoreau (1817–1862)
“Great Wits are sure to Madness near alli’d
And thin Partitions do their Bounds divide;
Else, why should he, with Wealth and Honour blest,
Refuse his Age the needful hours of Rest?”
—John Dryden (1631–1700)