## Testing properties in arbitrary planar graphs via random walks

by Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, and Christian Sohler.

#### Oded's comments

Most research regarding testing properties of graphs refers to the
adjacency matrix representation, which is suitable for dense graphs,
and an additional portion refers to the bounded-degree graph model.
The current work is an exception, being among the few works that
refer to a model of general graphs in which distances are measured in
terms of the actual edge density. I think that this model deserves far
more attention than it has received so far, which is one reason that I
like the current work.

The current work is in minority also in another sense:
It is among the few works that refer to a promise
on the structure of the input graph.
Specifically, it refers to the natural class (promise)
of planar graph. It turns out that this promise allows to
improve the complexity of the tester, and in this respect the
fact that the promise ios natural is of key importance.

#### The original abstract

We study the testability of hereditary properties in arbitrary planar graphs.
Our main result is a constant time testing of bipartiteness in arbitrary planar
graphs. The previous bound for this class of graphs was $O^{\ast}(\sqrt{n})$,
and the constant-time testability was only known for planar graphs with {\bf
bounded degree}. Previously used transformations of unbounded-degree sparse
graphs into bounded-degree sparse graphs cannot be used to reduce the problem
to the testability of bounded-degree planar graphs. Our approach extends to
arbitrary minor-free graphs.
Our algorithm is based on random walks. The challenge here is to analyze random
walks for a class of graphs that has good separators, i.e., bad expansion.
Standard techniques that use a fast convergence to a uniform distribution do
not work in this case. Informally, our analysis technique self-reduces the
problem of finding an odd length cycle in a multigraph $G$ induced by a
collection of cycles to another multigraph $G'$ induced by a set of shorter
odd-length cycles, in such a way that when a random walks finds a cycle in $G'$
with probability p, then it does so with probability $f(p)$ in $G$. This
reduction is applied until the cycles collapse to selfloops that can be easily
detected.

Back to
list of Oded's choices.