Example
Consider a grid graph with r rows and c columns; the number n of vertices equals rc. For instance, in the illustration, r = 5, c = 8, and n = 40. If r is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if c is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing S to be any of these central rows or columns, and removing S from the graph, partitions the graph into two smaller connected subgraphs A and B, each of which has at most n/2 vertices. If r ≤ c (as in the illustration), then choosing a central column will give a separator S with r ≤ √n vertices, and similarly if c ≤ r then choosing a central row will give a separator with at most √n vertices. Thus, every grid graph has a separator S of size at most √n, the removal of which partitions it into two connected components, each of size at most n/2.
The planar separator theorem states that a similar partition can be constructed in any planar graph. The case of arbitrary planar graphs differs from the case of grid graphs in that the separator has size O(√n) but may be larger than √n, the bound on the size of the two subsets A and B (in the most common versions of the theorem) is 2n/3 rather than n/2, and the two subsets A and B need not themselves form connected subgraphs.
Read more about this topic: Planar Separator Theorem
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)