Approximation algorithms for polynomial-expansion and low-density graphs
$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}}
\newcommand{\eps}{\varepsilon}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}$
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},
Set Cover, and Dominating Set problems,
among others. We also prove corresponding hardness of
approximation for some of these optimization problems, providing a
characterization of their intractability in terms of density.
PDF.
Slides: ESA 2015 talk (created and presented by Kent).
Last modified: Sun Sep 27 13:24:55 CDT 2015