Every property of outerplanar graphs is testable in O(poly(\log n)) queries

For a graph on $n$ vertices, and an integer $D$, let the $D$-local view of $G=(V,E)$ be the collection (multiset) of the unlabelled $n$ balls of distance $D$ around the vertices.

The main question that motivates this study is: what can be said about $G$ knowing only its $D$-local view for some constant $D$.

For constant bounded degree planar (or more generally hyperfinite) graphs, Newman-Sohler [2011] following a long sequence of work, show that for any $\epsilon > 0$, there is a $D$ such that the $D$-local view of the graph determines the graph up to the deletion / insertion of at most $\epsilon n$ edges. This in turn, implies that every property of planar (hyperfinite) graphs can be tested (in the sense of property testing, by constantly many queries.

What happens in non-bounded degree planar graphs? The answer is currently still open. However, we show, following Yoshida's results on forests, that the above phenomenon still holds for outerplanar graphs. The implication to testing is deteriorated, though. Testing now requires $O(poly(\log n))$ queries.

I will describe the ideas behind the two results, the later which is a joint work with Jasine Babu and Areej Khoury.