Ordered graphs, decompositions, algorithms and structures – GODASse

Storing a graph in a computer (von Newmann architecture) implicitly defines an ordering of its vertices. We observe that graph algorithms may benefit from a clever use of such an ordering. One can think of the strongly connected component algorithm (Kosaraju-Sahrir, 1981) for which linear time can be achieved if the vertices are ordered in a DFS manner. We also remark that vertex orderings are frequently used to characterize graph properties. These characterizations are based on the exclusion of so-called patterns, which are (small) graphs whose vertices are ordered. A popular example is the fact that the chromatic number of a graph is at most k if and only if its vertices can be ordered so that the forward path of length k is excluded.

Surprisingly, very little is known about ordered graphs and as of today, the theory of ordered graphs both from the combinatorial and algorithmic viewpoints, has not been investigated in a systematic way. The objective of this proposal is to fill this lack. The project will be organized in three working packages:
WP1- Ordered graph to characterize certificates of graph properties
WP2 - Theoretical and algorithmic aspects of ordered graphs
WP3 - Extensions of ordered graphs
We aim at proving combinatorial results on ordered graph and developing dedicated decomposition methods which will serve as the foundations for the design of efficient algorithms of (ordered) graphs.