Logical methods in Computer Science have a long history, as witnessed e.g. by the relative longevity of SQL in relational database management. More recently, Courcelle’s theorem, which combines second-order logic and tree decompositions of graphs, showed that a many NP-complete algorithmic problems in graph theory can be solved in polynomial time on graphs with bounded tree-width (and even on graphs with bounded clique-width). At the heart of the latter result is the notion of monadic second-order transductions, which are a way to encode a graph within a structure using coloring and monadic second-order logic formulas. In this presentation we consider first-order transductions, for which the formulas have to be first-order formulas. As a counterpart for this strong restriction, many algorithmic problems become fixed parameter tractable when restricted to nowhere dense classes, which include classes excluding a topological minor thus, in particular, classes of planar graphs and classes of graphs with bounded degrees.
In this setting, the main challenge is to extend results obtained in the sparse setting (for bounded expansion classes and nowhere dense classes) to the dense setting, in a similar way the results about monadic second-order model checking have been extended from classes with bounded tree-width to classes with bounded clique-width.