Graphs, Algorithms and TOpology – GATO

The concept of graph is ubiquitous in modern science: it is a basic notion in combinatorics and algorithmics and it is used as a tool for abstraction in an ever increasing variety of contexts, from social networks to biological process modelling. While the theory of graphs is rich and interesting in general, it also appears clearly that in many applicative contexts, the graphs of interest come with some extra structure that needs to be taken into account, both to improve the focus of the modelisation and to benefit from potentially more efficient algorithmic solutions. Examples range from the celebrated power laws and small-world properties of networks to the dimension reduction phenomenon in geometric data.

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.

In the last few years the members of our project have been involved in various deep and independent algorithmic and combinatorial progresses that directly regard maps: we may quote the optimization of curves on surfaces, succinct data structures for meshes, dynamic programming on bounded genus graphs, or bijective decompositions of various families of planar maps, among several others. We believe our group has the right size and expertise to attack the hard challenges raised by the handling of maps on non-trivial surfaces. Let us succinctly describe some of the problematics we want to consider.

The combinatorial structure of planar maps is now well understood thanks to the notion of Schnyder woods. One of our main objectives is to extend Schnyder woods to non-planar maps. Another fundamental parameter for maps on higher genus surfaces is the minimal length of a non-contractible cycle. This parameter, called the edge-width, measures the local planarity of a map. Since a typical (random) map has a large edge-width it is relevant to study the dependency of structural properties on this parameter. Apart from Schnyder woods and the edge-width, we want to concentrate on specific families of maps, such as irreducible triangulations, for which topological decompositions such as pants decompositions appear more appropriate for the study of their structure. Understanding the structure of maps is crucial when enumerating, sampling or even representing maps. The representation of non-planar maps, i.e. their geometric embedding, for the purpose of visualization, texture mapping, or network analysis is another of our challenges. In parallel to these theoretical investigations, we wish to implement the state of the art concerning algorithms for maps on surfaces and fix the knowledge in this domain in a dedicated handbook.