Structural graph theory has proved to be a powerful tool for coping<br/>with computational intractability. It provides a wealth of <br/>concepts and results that can be used to design efficient algorithms for<br/>hard computational problems on specific classes of graphs that<br/>occur naturally in applications.<br/><br/>In many applications in computer science, the natural mathematical<br/>model are directed graphs. Unfortunately, research in<br/>structural graph theory has so far almost exclusively focussed on<br/>undirected graphs and no structure theory for directed graphs<br/>comparable to the tree-width and graph minors based approach for<br/>undirected graphs has been developed that would provide for a similar<br/>set of tools and concepts to deal with computational problems on<br/>directed graphs. <br/><br/>The objective of this proposal is to develop such a structure<br/>theory aimed specifically at algorithmic applications on directed<br/>graphs. The novelty of our approach is that<br/><br/>a) it is based on directed minors which allows us to avoid<br/> the algorithmic problems faced by existing digraph width<br/> measures and has not been studied before in this context and <br/><br/>b) it facilitates our recent proof of the excluded directed<br/> grid theorem which is likely to allow entirely new algorithmic<br/> techniques for directed graphs.<br/><br/>The focus of the project is on the development of the structural<br/>foundations and algorithmic techniques for designing efficient algorithms<br/>for a wide range of algorithmic digraph problems. In particular, we<br/>will use an approach based on logical definability for developing such<br/>algorithmic techniques. <br/><br/>Furthermore, we will apply our methods to two specific application<br/>areas, model-checking in computer-aided verification and inference<br/>problems in Bayesian networks.