  In this paper we use several of the key ideas from Bidimensionality to give a
new generic approach to design EPTASs and subexponential time parameterized
algorithms for problems on classes of graphs which are not minor closed, but
instead exhibit a geometric structure. In particular we present EPTASs and
subexponential time parameterized algorithms for Feedback Vertex Set, Vertex
Cover, Connected Vertex Cover, Diamond Hitting Set, on map graphs and unit disk
graphs, and for Cycle Packing and Minimum-Vertex Feedback Edge Set on unit disk
graphs. Our results are based on the recent decomposition theorems proved by
Fomin et al [SODA 2011], and our algorithms work directly on the input graph.
Thus it is not necessary to compute the geometric representations of the input
graph. To the best of our knowledge, these results are previously unknown, with
the exception of the EPTAS and a subexponential time parameterized algorithm on
unit disk graphs for Vertex Cover, which were obtained by Marx [ESA 2005] and
Alber and Fiala [J. Algorithms 2004], respectively.
  We proceed to show that our approach can not be extended in its full
generality to more general classes of geometric graphs, such as intersection
graphs of unit balls in R^d, d >= 3. Specifically we prove that Feedback Vertex
Set on unit-ball graphs in R^3 neither admits PTASs unless P=NP, nor
subexponential time algorithms unless the Exponential Time Hypothesis fails.
Additionally, we show that the decomposition theorems which our approach is
based on fail for disk graphs and that therefore any extension of our results
to disk graphs would require new algorithmic ideas. On the other hand, we prove
that our EPTASs and subexponential time algorithms for Vertex Cover and
Connected Vertex Cover carry over both to disk graphs and to unit-ball graphs
in R^d for every fixed d.
