ANR Project EGOS (2012-2016) : ANR-12-JS02-002-01

Embedded Graphs and their Oriented Structures

In the plane, many families of graphs have oriented structures, which are orientations and colorings of the edges of the graph satisfying a particular local property. For example: 2-connected bipartite planar graphs admit 2-orientations, 3-connected planar graphs admit Schnyder woods, 4-connected planar triangulations admit transversal structures. These structures are in bijection with several combinatorial objects like contact system of polygons, TD-Delaunay triangulations, or Dyck words. They also appear to have various computer science applications such as succinct encoding, graph drawing, graph spanners, etc.

This project aims at generalizing these oriented structures to higher genus surfaces and higher dimensional objects. Recent results have been obtained in this direction, thus opening new axes of research. The first steps of the project consist in finding the natural generalization of the considered structures, proving their existence, and studying their properties. Then the goal is to find bijections and applications of these objects that extend the planar case.