A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error

We consider one-sided error property testing of F-minor freeness in bounded-degree graphs for any finite family of graphs F that contains a minor of K2,k, the k-circus graph, or the (k × 2)-grid for any k ∈ N. This includes, for instance, testing whether a graph is outerplanar or a cactus graph. The query complexity of our algorithm in terms of the number of vertices in the graph, n, is O(n2/3/5). Czumaj et al. (2014) showed that cycle-freeness and Ck-minor freeness can be tested with query complexity O(n) by using random walks, and that testing H-minor freeness for any H that contains a cycles requires (n) queries. In contrast to these results, we analyze the structure of the graph and show that either we can find a subgraph of sublinear size that includes the forbidden minor H, or we can find a pair of disjoint subsets of vertices whose edge-cut is large, which induces an H-minor.