APPROXIMATION ALGORITHMS FOR POLYNOMIAL-EXPANSION AND LOW-DENSITY GRAPHS

We investigate the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, includes planar graphs, and in particular is a subset of the family of graphs that have polynomial expansion. We present efficient (1 + epsilon)-approximation algorithms for polynomial expansion graphs for unweighted Independent Set, Set Cover, and Dominating Set problems, among others, and these results seem to be new. Naturally, PTASs for these problems are known for subclasses of this graph family. These results have immediate applications in the geometric domain. For example, the new algorithms yield the only PTAS known for covering points by fat triangles (that are shallow). We also prove corresponding hardness of approximation for some of these optimization problems, characterizing their intractability with respect to density. For example, we show that there is no PTAS for covering points by fat triangles if they are not shallow, thus matching our PTAS for this problem with respect to depth.