| On the Cover Time of Planar Graphs (2000) | |||||||||
Abstract | |||||||||
| The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all the vertices. It is known that the cover time on any n-vertex, connected graph is at least (1+o(1))nlogn and at most (1+o(1))(4/27)n3. This paper proves that for bounded-degree planar graphs the cover time is at least cn(logn)2, and at most 6n2, where c is a positive constant depending only on the maximal degree of the graph. The lower bound is established via use of circle packings. | |||||||||
Publication details | |||||||||
| |||||||||