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:
“What comes over a man, is it soul or mind
That to no limits and bounds he can stay confined?
You would say his ambition was to extend the reach
Clear to the Arctic of every living kind.
Why is his nature forever so hard to teach
That though there is no fixed line between wrong and right,
There are roughly zones whose laws must be obeyed?”
—Robert Frost (1874–1963)