A classic result of Courcelle asserts that every monadic second order logic (MSOL) formula can be decided in linear time for graphs with bounded tree-width. This result unified most of algorithmic results for graphs with bounded tree-width and was followed by many results of the same favor.In the beginning of the talk, we focus on classes of graphs with bounded expansion and classes of nowhere dense-graphs which have recently been introduced by Nesetril and Ossona de Mendez. These classes of graphs include and generalize proper minor-closed classes of graphs, classes of graphs with locally bounded tree-width or locally excluding a minor. We will then present a joint result with Dvorak and Thomas that every first order logic (FOL) formula can be decided in linear time for graphs with bounded expansion and in almost linear time for nowhere-dense graphs. The presented results translate to classes of relational structures with Gaifman graphs from such classes of graphs.
At the end of the talk, we consider classes of graphs with bounded clique-width. We consider an extension of $MSOL_1$ formulas where a polynomially bounded number of quantifiers over vertex sets can be added, which we call $F-MSOL_1$ formulas. The problem whether an input graph is hamiltonian can be expressed by an $F-MSOL_1$ formula, but not by an $MSOL_1$ formula. We will next present a joint result with Hlineny and Obdrzalek that every $F-MSOL_1$ formula can be decided in polynomial time for graphs with bounded clique-width.