  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 this topic: given an ordered graph of size $n$,
how fast can we detect whether a fixed pattern of size $k$ is present?
  Following the literature on graph classes recognition, we first look for
patterns that can be detected in linear time. We prove, among other results,
that almost all patterns on three vertices (which capture many interesting
classes, such as interval, chordal, split, bipartite, and comparability graphs)
fall in this category. Then, in a finer-grained complexity perspective, we
prove conditional lower bounds for this problem. In particular we show that for
a large family of patterns on four vertices it is unlikely that subquadratic
algorithm exist. Finally, we define a parameter for patterns, the merge-width,
and prove that for patterns of merge-width $t$, one can solve the problem in
$O(n^{ct})$ for some constant~$c$. As a corollary, we get that detecting
outerplanar patterns and other classes of patterns can be done in time
independent of the size of the pattern.
