For the class of structures with bounded degree and FO queries
the model checking problem is in FPL [1]} and there also are constant delay
enumeration algorithms [2]}, [3]}. In the case of structures
of bounded treewidth and FO queries (actually even MSO queries with
first-order free variables) the model checking problem is also in FPL [4]}
and there are constant delay enumeration
algorithms [5]}, [6]}. For classes of structures with bounded
expansion the model checking problem for FO queries was recently shown to be
in FPL [7]}, [8]}.
