Welcome to ANR GATO

ANR project GATO (Graphes Algorithmes et TOpologie) 2016-2020 : ANR-16-CE40-0009-01

Our project focuses on the extra combinatorial and topological structure carried by graphs coming with an embedding on a surface of low genus. The resulting objects, called "maps", are fundamental in computer graphics and geometric modelling where maps underlie all classical data structures for the manipulation of 2d meshes. Maps also play an important role in the celebrated graph minor theory of Robertson and Seymour and in its algorithmical consequences: a remarkable outcome of this theory is that for many problems, any improvement on their complexity when restricted to graphs with bounded genus directly extends to the (much wider) class of graphs with forbidden minors. Combinatorial properties of maps have also proven to be very relevant to the study of random models of surfaces as considered in the probabilistic community and in physics in relation with mathematical models of quantum gravity.