A Sublinear Tester for Outerplanarity

We consider one-sided error property testing of $\calF$-minor freeness in bounded-degree graphs for any finite family of graphs $\calF$ 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.

This is joint work with Hendrik Fichtenberger, Yadu Vasudev and Maximilian Wötzel.