The Library
Planar graphs : random walks and bipartiteness testing
Tools
Czumaj, Artur, Monemizadeh, Morteza, Onak, Krzysztof and Sohler, Christian (2011) Planar graphs : random walks and bipartiteness testing. In: 52nd Annual Symposium on Foundations of Computer Science (FOCS), Palm Springs, CA, 22-25 Oct. 2011. Published in: Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on pp. 423-432. ISBN 9781457718434. doi:10.1109/FOCS.2011.69 ISSN 0272-5428.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1109/FOCS.2011.69
Abstract
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(√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 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. Roughly speaking, 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 >; 0, then it does so with probability λ(p) >; 0 in G. This reduction is applied until the cycles collapse to self-loops that can be easily detected.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on | ||||
Publisher: | IEEE | ||||
ISBN: | 9781457718434 | ||||
ISSN: | 0272-5428 | ||||
Book Title: | 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | ||||
Official Date: | October 2011 | ||||
Dates: |
|
||||
Page Range: | pp. 423-432 | ||||
DOI: | 10.1109/FOCS.2011.69 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 52nd Annual Symposium on Foundations of Computer Science (FOCS) | ||||
Type of Event: | Conference | ||||
Location of Event: | Palm Springs, CA | ||||
Date(s) of Event: | 22-25 Oct. 2011 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |