| COMMUNICATIONS in PROBABILITY ON THE COVER TIME OF PLANAR GRAPHS (2000) | |||||||||||||||
Abstract | |||||||||||||||
| effective resistance, commute time, hitting time, difference time, circle packing, triangulation 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) � n log n 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(log n) 2,andatmost6n 2,wherec is a positive constant depending only on the maximal degree of the graph. The lower bound is established via use of circle packings. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||