Abstract
We review recent results for sublinear-time testing of fundamental graph properties in sparse graphs.
We consider the problem in which an input graph G is represented as an adjacency matrix and we're asking a question whether G has a given property P or is "far" from any graph satisfying P. The central question in this area is which properties can be tested very quickly, in particular, in constant-time, independently of the size of the input graph.
We will present recent advances in this area, focusing on planar graphs and graphs with poor expansion properties.
This is talk is based on joint papers with Christian Sohler and others.