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:
“Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man’s appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded.”
—Abraham Lincoln (1809–1865)
“At bounds of boundless void.”
—Samuel Beckett (1906–1989)