Reinhard Diestel. Graph Theory.
Springer-Verlag. Graduate Texts in Mathematics.

Relevant Surveys: Martin Grohe. Logic, Graphs and Algorithms.
In J.Flum, E.Gr?¤del, T.Wilke (Eds), Logic and Automata â?? History and Perspectives, Amsterdam University Press, 2007.

Stephan Kreutzer. Algorithmic Meta Theorems.

Anuj Dawar: Structure and Specification as Sources of Complexity. FSTTCS 2009: Leibniz International Proceedings in Informatics (LIPIcs), 4:407-416.

References for specific results:

B. Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 2, pages 194 â?? 242. Elsevier, 1990.

D. Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 5:505â??526, 1996.

M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM, 48:1148 â?? 1206, 2001.

J. Flum and M. Grohe. Fixed-parameter tractability, definability, and model checking. SIAM Journal on Computing, 31:113 â?? 145, 2001.

A. Dawar, M. Grohe, and S. Kreutzer. Locally excluding a minor. In Proc. 22nd IEEE Symp. on Logic in Computer Science, pages 270â??279, 2007.

A. Dawar and S. Kreutzer. Domination problems in nowhere-dense classes of graphs. FSTTCS 2009: Leibniz International Proceedings in Informatics (LIPIcs) 4:157-168.