  We consider properties of edge-colored vertex-ordered graphs, i.e., graphs
with a totally ordered vertex set and a finite set of possible edge colors. We
show that any hereditary property of such graphs is strongly testable, i.e.,
testable with a constant number of queries. We also explain how the proof can
be adapted to show that any hereditary property of $2$-dimensional matrices
over a finite alphabet (where row and column order is not ignored) is strongly
testable. The first result generalizes the result of Alon and Shapira [FOCS'05,
SICOMP'08], who showed that any hereditary graph property (without vertex
order) is strongly testable. The second result answers and generalizes a
conjecture of Alon, Fischer and Newman [SICOMP'07] concerning testing of matrix
properties.
  The testability is proved by establishing a removal lemma for vertex-ordered
graphs. It states that for any finite or infinite family $\mathcal{F}$ of
forbidden vertex-ordered graphs, and any $\epsilon > 0$, there exist $\delta >
0$ and $k$ so that any vertex-ordered graph which is $\epsilon$-far from being
$\mathcal{F}$-free contains at least $\delta n^{|F|}$ copies of some
$F\in\mathcal{F}$ (with the correct vertex order) where $|F|\leq k$. The proof
bridges the gap between techniques related to the regularity lemma, used in the
long chain of papers investigating graph testing, and string testing
techniques. Along the way we develop a Ramsey-type lemma for $k$-partite graphs
with "undesirable" edges, stating that one can find a Ramsey-type structure in
such a graph, in which the density of the undesirable edges is not much higher
than the density of those edges in the graph.
