We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2^{O(n^{1-1/d})} for any fixed dimension d \geq 2 for many well known graph problems, including Independent Set, r-Dominating Set for constant r, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms work on the graph itself , i.e.,  do not require any geometric information . Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into d-dimensional grids, and it allows us to derive matching 2^{\Omega(n^{1-1/d})} lower bounds under the Exponential Time Hypothesis even in the much more restricted class of d-dimensional induced grid graphs.
We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2^{O(n^{1-1/d})} for any fixed dimension d \geq 2 for many well known graph problems, including Independent Set, r-Dominating Set for constant r, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms are representation-agnostic , i.e., they work on the graph itself and do not require the geometric representation . Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into d-dimensional grids, and it allows us to derive matching 2^{\Omega(n^{1-1/d})} lower bounds under the Exponential Time Hypothesis even in the much more restricted class of d-dimensional induced grid graphs.
R
work on the graph itself
are representation-agnostic
A
they work on the graph itself and
R
any geometric information
the geometric representation