Hendrik Fichtenberger, Reut Levi, Yadu Vasudev and Maximilian Wotzel
A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With
One-Sided Error

Abstract: We consider one-sided error property testing of $\mathcal{F}$-minor
freeness in bounded-degree graphs for any finite family of graphs
$\mathcal{F}$ that contains a minor of $K_{2,k}$, the $k$-circus graph,
or the $(k\times 2)$-grid for any $k\in\mathbb{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 $\tilde{O}(n^{2/3} / \epsilon^5)$. Czumaj et~al.\
(2014) showed that cycle-freeness and $C_k$-minor freeness can be tested
with query complexity $\tilde{O}(\sqrt{n})$ by using random walks, and
that testing $H$-minor freeness for any $H$ that contains a cycles
requires $\Omega(\sqrt{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.