We study property testing in the model of bounded degree graphs. It
is well known that in this model many graph properties cannot be
tested with a constant number of queries and it seems reasonable to
conjecture that only few are testable with o(sqrt{n}) queries.
Therefore in this paper we focus our attention on testing graph properties for special classes of graphs, with the aim of proving the testability of general families of graph properties under the assumption that the input graph belongs to a (natural) family of graphs. We call a graph family non-expanding if every graph in this family has a weak expansion (its expansion is O(1/log^2n), where n is the graph size). A graph family is hereditary if it is closed under
vertex removal. Similarly, a graph property is hereditary if
it is closed under vertex removal. We call a graph property \Pi to
be testable for a graph family F if for every graph G \in F, in time independent of the size of G we can distinguish between the case when $G$ satisfies property \Pi and when it is far from every graph satisfying property \Pi. In this paper we prove that:

In the bounded degree graph model, any hereditary property is
testable if the input graph belongs to a hereditary and
non-expanding family of graphs.

Our result implies that, for example, any hereditary property (e.g.,
k-colorability, H-freeness, etc.) is testable in the bounded
degree graph model for planar graphs, graphs with bounded genus,
interval graphs, etc. No such results have been known before, and
prior to our work, very few graph properties have been known to be
testable for general graph classes in the bounded degree graph
model.