Approximation algorithms for NP-complete problems on planar graphs
Brenda S. Baker · Journal of the ACM · 1994
This paper describes a general technique that can be used to obtain approximation schemes for various NP-complete problems on planar graphs.The strategy depends on decomposing a planar graph into subgraphs of a form we call k-outerplanar.For fixed k, the problems of interest are solvable optimally in linear time on k-outerplanar graphs by dynamic programming.For general planar graphs, if the problem is a maximization problem, such as maximum independent set, this technique gives for each k a linear time algorithm that produces a solution whose size is at least k/(k + 1)optimal.If the problem is a minimization problem, such as minimum vertex cover, it gives for each k a linear time algorithm that produces a solution whose size is at most (k + 1)/k optimal.Taking k = [c log log nl or k = [c log nl, where n is the number of nodes and c is some constant, we get polynomial time approximation algorithms whose solution sizes converge toward optimal as n increases.The class of problems for which this approach provides approximation schemes includes maximum independent set, maximum tile salvage, partition into triangles, maximum H-matching, minimum vertex cover, minimum dominating set, and minimum edge dominating set.For these and certain other problems, the proof of solvability on k-outerplanar graphs also enlarges the class of planar gmphs for which the problems are known to be solvable in polynomial time.