Every minor-closed property of sparse graphs is testable

Suppose G is a graph of bounded degree d, and one needs to remove ϵn of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around vertices of G is far from the statistics of local neighborhoods around vertices of any planar graph G′. In fact, a similar result is proved for any minor-closed property of bounded degree graphs.The main motivation of the above result comes from theoretical computer-science. Using our main result we infer that for any minor-closed property P, there is a constant time algorithm for detecting if a graph is “far” from satisfying P. This, in particular, answers an open problem of Goldreich and Ron [STOC 1997] [20], who asked if such an algorithm exists when P is the graph property of being planar. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.