We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nešetřil and Ossona de Mendez. This generalizes several results from the literature, because many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We deduce that there is an almost linear-time algorithm for deciding FO properties in classes of graphs with locally bounded expansion. More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FO property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their simultaneous addition results in a graph in the class. All our results also hold for relational structures and are based on the seminal result of Nešetřil and Ossona de Mendez on the existence of low tree-depth colorings.

A result of Plotkin, Rao, and Smith implies that graphs with polynomial expansion have strongly sublinear separators. We prove a converse of this result showing that hereditary classes of graphs wi...

An immersion of a graph H into a graph G is a one-to-one mapping f: V (H) → V (G) and a collection of edge-disjoint paths in G, one for each edge of H, such that the path P _uv corresponding to edge uv has endpoints f(u) and f(v). The immersion is strong if the paths P _uv are internally disjoint from f(V (H)). It is proved that for every positive integer Ht, every simple graph of minimum degree at least 200t contains a strong immersion of the complete graph K _t . For dense graphs one can say even more. If the graph has order n and has 2cn ² edges, then there is a strong immersion of the complete graph on at least c ² n vertices in G in which each path P _uv is of length 2. As an application of these results, we resolve a problem raised by Paul Seymour by proving that the line graph of every simple graph with average degree d has a clique minor of order at least cd ^3/2, where c>0 is an absolute constant. For small values of t, 1≤t≤7, every simple graph of minimum degree at least t−1 contains an immersion of K _t (Lescure and Meyniel [13], DeVos et al. [6]). We provide a general class of examples showing that this does not hold when t is large.