### Abstract

We investigate the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, and includes planar graphs. This family of graphs has some interesting properties, and in particular, it is a subset of the family of graphs that have polynomial expansion. We present efficient (1+ε)-approximation algorithms for polynomial expansion graphs, for Independent Set, Set Cover, and Dominating Set problems, among others, and these results seem to be new. Naturally, PTAS’s for these problems are known for subclasses of this graph family. These results have immediate interesting 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.

Original language | English (US) |
---|---|

Title of host publication | Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings |

Editors | Nikhil Bansal, Irene Finocchi |

Publisher | Springer-Verlag |

Pages | 717-728 |

Number of pages | 12 |

ISBN (Print) | 9783662483497 |

DOIs | |

State | Published - Jan 1 2015 |

Event | 23rd European Symposium on Algorithms, ESA 2015 - Patras, Greece Duration: Sep 14 2015 → Sep 16 2015 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 9294 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 23rd European Symposium on Algorithms, ESA 2015 |
---|---|

Country | Greece |

City | Patras |

Period | 9/14/15 → 9/16/15 |

### Keywords

- Computational geometry
- Hardness of approximation
- SETH

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Approximation algorithms for Polynomial-Expansion and Low-Density graphs'. Together they form a unique fingerprint.

## Cite this

*Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings*(pp. 717-728). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294). Springer-Verlag. https://doi.org/10.1007/978-3-662-48350-3_60