Deciding first-order properties of locally tree-decomposable structures

Markus Frick, Martin Grohe

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 c…