observed that the separator theorem may be used to obtain polynomial time approximation schemes for NP-hard optimization problems on planar graphs such as finding the maximum independent set. Specifically, by truncating a separator hierarchy at an appropriate level, one may find a separator of size O(n/\sqrt{\log n}) the removal of which partitions the graph into subgraphs of size at most c\log n, for any constant c. By the four-color theorem, there exists an independent set of size at least n/4, so the removed nodes form a negligible fraction of the maximum independent set, and the maximum independent sets in the remaining subgraphs can be found independently in time exponential in their size. By combining this approach with later linear-time methods for separator hierarchy construction and with table lookup to share the computation of independent sets between isomorphic subgraphs, it can be made to construct independent sets of size within a factor of 1-1/\sqrt{\log n} of optimal, in linear time. However, for approximation ratios even closer to one than this factor, a later approach of (based on tree-decomposition but not on planar separators) provides better tradeoffs of time versus approximation quality.
