Home | Bookmarks | Papers | Blog |

Sariel Har-Peled and Kent Quanrud.

We study the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, and includes planar graphs. We prove that such graphs have small separators. Next, we present efficient $(1+\eps)$-approximation algorithms for these graphs, for \ProblemC{Independent Set},

PDF.

Slides: ESA 2015 talk (created and presented by Kent).

Last modified: Sun Sep 27 13:24:55 CDT 2015