Local Explorations of Planar Graphs and Fast Property Testing
Artur Czumaj
University of Warwick
We will discuss recent results about testing properties in planar graphs using local exploration. We say a graph G is epsilon-far from satisfying a property P if one has to modify at least an epsilon-fraction of the edges in G to obtain a graph with property P. A few years ago, we have shown that in a planar graph G with constant maximum degree, for every hereditary property P, we can distinguish between the case that G has property P and G is epsilon-far from property P in time that is independent of the size of G, and is only a function of epsilon. In this talk we will discuss extensions of this result to arbitrary planar graphs (with arbitrary maximum degree).