Once we have a quantifier-free query, constant delay enumeration could also
be obtained using the characterization of bounded expansion based on low tree
depth colorings. Indeed, using this characterization one can easily show that
enumerating a quantifier-free query over structures of bounded expansion
amounts in enumerating an MSO query over structures of bounded tree-width and
for those known algorithms exist [1]}, [2]}. However, the known
enumeration algorithms of MSO over structures of bounded treewidth are rather
complicated while our direct approach is fairly simple. Actually, our proof
shows that constant delay enumeration of FO queries over structures of
bounded treewidth can be done using simpler algorithms than for MSO queries. Moreover,
it gives a constant delay algorithm outputting the solutions in lexicographical
order. No such algorithms were known for FO queries over structures of bounded
treewidth. In the bounded degree case, both enumeration algorithms
of [3]}, [4]} output their solutions in lexicographical
order.
