  We introduce the concept of a class of graphs, or more generally, relational
structures, being locally tree-decomposable. There are numerous examples of
locally tree-decomposable classes, among them the class of planar graphs and
all classes of bounded valence or of bounded tree-width. We also consider a
slightly more general concept of a class of structures having bounded local
tree-width.
  We show that for each property P of structures that is definable in
first-order logic and for each locally tree-decomposable class C of graphs,
there is a linear time algorithm deciding whether a given structure A in C has
property P. For classes C of bounded local tree-width, we show that for every
k\ge 1 there is an algorithm that solves the same problem in time
O(n^{1+(1/k)}) (where n is the cardinality of the input structure).
