Pattern detection in ordered graphs

A popular way to define or characterize graph classes is via forbidden subgraphs or forbidden minors. These characterizations play a key role in graph theory, but they rarely lead to efficient algorithms to recognize these classes. In contrast, many essential graph classes can be recognized efficiently thanks to characterizations of the following form: there must exist an ordering of the vertices such that some ordered pattern does not appear, where a pattern is basically an ordered subgraph. These pattern characterizations have been studied for decades, but there have been recent efforts to better understand them systematically. In this paper, we focus on a simple problem at the core of th…