Since the submission of this work, the result has been extended to a larger
class of structures. In [1]} the class of nowhere dense graphs was
introduced and it generalizes the notion of bounded expansion. It has
been shown that the model checking problem of first-order logic can be done in
nearly linear time (i.e. for any \(\epsilon >0\)  it can be done in
\(O(n^{1+\epsilon })\) ) over any nowhere dense class of
graph [2]}. Recently an enumeration procedure has
been proposed for first-order queries over nowhere dense graph classes, with a
nearly linear preprocessing time and constant
delay [3]}.
