A Sublinear Tester for Outerplanarity

03/05/2018 - 12:00
Speaker: 
Seminar: 
מיקום: 
Abstract: 

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.