Artur Czumaj
Testing H-freeness in Arbitrary Planar Graphs in Constant Time (Using Random Graph Exploration)

Abstract: We consider property testing in general planar graphs,
without any bounds for vertex degrees. While testing graph properties
in bounded-degree planar graphs is quite well understood, almost
nothing is known in the case of general graphs. In this talk, I will
prove that the fundamental property of being H-free is constant time
testable for every fixed connected subgraph H, in the model when the
algorithm can sample random vertices from the input graph and random
neighbors of a vertex. Our approach extends to arbitrary minor-free
graphs.  This is a joint work with Christian Sohler.