Once a graph theoretical formulation of a real world situation has been established, it is a challenging task to efficiently solve various optimisation problems on the resulting graphs. An example of such an optimisation problem in a communication network, is to place a minimum number of communication antennas to cover all important locations with wireless network. In its graph theoretic formulation the problem corresponds to the problem of finding a small dominating set in the network graph, that is, a set of vertices which is connected to all other vertices by an edge.
It has long been realised that a large class of important algorithmic problems seems to evade all attempts of solving them efficiently in general. The meaning of efficiency and tractability varies. For example, it may be polynomial time solvability, fixed-parameter tractability, or polynomial time approximability to some ratio. The earlier mentioned dominating set problem on the class of all graphs is NP-hard, W[2]-hard and Log-APX-hard, hence considered intractable with respect to all of the above notions (here NP, W[2] and Log-APX are classes of problems that share specific properties regarding their complexity). However, on restricted graph classes, the complexity of a problem may be quite different from the general worst-case complexity. In particular, instances of graphs arising in applications often have more structure than general graphs. For instance, road or railway maps correspond to nearly planar graphs and telecommunication networks are modelled by sparse graphs, that is, by graphs with a moderate number of edges.
Researchers have studied many structural properties of graphs which can be used to design efficient algorithms for otherwise hard problems. Among the most important ones are properties of planar graphs or, more generally, properties of graph classes that exclude a minor. Robertson and Seymour developed a celebrated structure theory of graphs with excluded minors which had an immense influence on the design of efficient algorithms. In particular, the concept of tree-width, which they introduced as part of their graph minors project, proved extremely valuable in the algorithmic context.
Recent results indicate that a more fundamental property of graphs leads to very general algorithmic tractability results. Nesetril and Ossona de Mendez introduced a general model of uniform sparseness in graphs, called nowhere denseness. Many familiar classes of sparse graphs such as planar graphs, bounded degree graphs and classes that exclude minors, are nowhere dense. The new concept turns out to be very robust and seems to capture a natural property of graphs, as witnessed by the fact that nowhere dense classes can equivalently be characterised in several completely different ways, arising independently in diverse contexts. This has direct algorithmic consequences, as each characterisation yields its own algorithmic technique. On the other hand, several hardness results indicate that nowhere dense classes form a limit for many algorithmic methods based on sparseness of graphs.
A large part of my research is concerned with the application of the newly developed methods for nowhere dense graphs to efficiently solve specific computational problems arising in different areas of computer science, in particular in parameterized complexity theory, approximation algorithms and distributed computing. On the other hand, I want to extend the logic based approach to develop a general and broad algorithmic graph structure theory for classes that are even more general than nowhere dense classes of graphs.