Problems that are intractable in general are at times solvable on highly structured graphs such as trees and their generalizations. In choosing classes of graphs for which to develop algorithms, it is useful to observe that various structural properties of graphs can be identified as natural parameters and as a consequence lead to elegant solutions using techniques drawn from the field of parameterized complexity, introduced by Downey and Fellows. This area is concerned with solving parameterized versions of problems (versions in which the parameter or parameters are part of the input), with the goal of obtaining algorithms that run in time polynomial in the size of the input but possibly exponential in the parameter(s). Such results are of interest not only for small parameter values but also for the approximation algorithms derived therefrom.
Making use of both known and newly derived structure, I have devised algorithms for a large range of problems, including network flow, interval routing, embedding problems, graph drawing, and games. Many of these problems are in general NP-complete; algorithms are obtained for special classes of graphs (for which special structural properties are derived and used), for parameterized versions of problems, or as approximate solutions.