Using the seminal work of Damaschke (1990) we propose a systematic study of structured graph classes that can be defined by the existence of an ordering of the vertices avoiding some forbidden patterns. Among these classes we have : bipartite, trees, split, chordal, interval, comparability, outerplanar...

Hell, Mohar and Rafiey (2014) proved that for patterns on 3 vertices, the given class is always polynomially recognizable. We propose a simpler proof of this fact and give the complete list of graph classes defined with 2 patterns on 3 vertices. There exists classes defined by a 4 vertices pattern which are NP-complete to recognize.
Furthermore Duffus, Ginn and Rödl (1995) showed that for almost all 2-connected patterns the associated class is NP-Complete to recognize. But following Nesestril (2017), it seems that on this problem there is no dichotomy.

Furthermore we show that most of the good recognition algorithms use this notion of patterns.
We end with an application of this framework to distributed local recognition and some open problems.

Joint work with Y. BoufKad, P. Charbit and M. Habib.