Welcome on ANR Digraphs website !
DIGRAPHS (Directed graphs) is a research project funded by Agence Nationale de la Recherche (ANR-19-CE48-0013). It gathers researchers from three laboratories: LIRMM (Equipe AlGCo), LIP (Equipe MC2, ENS Lyon), et l’I3S (Equipe COATI, Sophia Antipolis).
It started in January 2020.
Scientific description
Directed graphs (digraphs for short) are naturally used to model many real-world problems. For example, many graphs modelling networks are by essence directed (web graph, twitter graph, . . . ). To address those problems, we need to have a better understanding of structural and algorithmic aspects of digraphs. However, for various reasons, digraph theory is a lot less developed than (undirected) graph theory. One of the reasons is that, very often, a problem on graphs corresponds to a particular case (in general for symmetric digraphs) of an analogue problem on digraphs. Therefore digraph problems are intrinsically more difficult than graph problems.
The objectives of the project is to make some advances on digraph theory in order to get a better understanding of important aspects of digraphs and to have more insight on the differences and the similarities between graphs and digraphs. We will mainly focus on digraph partition problems.
On the second hand, we will consider many results on graphs, find their (possibly many) formulations in terms of digraphs and see if and how they can be extended. Studying such extensions has been occasionally done, but the point here is to do it in a kind of systematic way.
