Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We initiate the study of the testability of properties in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time. The previous bound for this class of graphs was O-tilde(sqrt(n)), and the constant-time testability was only known for planar graphs with 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 is here 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. Roughly speaking, our analysis technique self-reduces the problem of ï¬ nding 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 ï¬ nds a cycle in G′ with probability p>0, then it does so with probability lambda(p)>0 in G. This reduction is applied until the cycles collapse to self-loops that can be easily detected.

Questions and Answers

You need to be logged in to be able to post here.