Every Minor-Closed Property of Sparse Graphs is Testable

Itai Benjamini, Oded Schramm, Asaf Shapira

Suppose $G$ is a graph with degrees bounded by $d$, and one needs to remove more than $\epsilon n$ of its edges in order to make it planar. We show that in this case the statistics of loca…