Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 5 (2000) > Paper 10 open journal systems 


On the Cover Time of Planar Graphs

Johan Jonasson, Chalmers University of Technology
Oded Schramm, Microsoft Research


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.


Full text: PDF

Pages: 85-90

Published on: May 5, 2000
Bibliography
  1. D. ALDOUS, On the Time Taken by Random Walks on Finite Groups to Visit Every State, Wahrsch. Verw. Gebeite 62 (1983), 361-374. Math. Review Link MR 84i:60013.
  2. D. ALDOUS AND J. A. FILL, ``Reversible Markov Chains and Random Walks on Graphs'' (book draft), October 1999.
    http://www.stat.berkeley.edu/ aldous/book.html Math Review link not available.
  3. I. BENJAMINI AND O. SCHRAMM, Harmonic Functions on Planar and Almost Planar Graphs and Manifolds, Via Circle Packings, Invent. Math. 126 (1996), 565-587. MR 97k:31009
  4. G. R. BRIGHTWELL AND E. R. SCHEINERMAN Representations of planar graphs, SIAM J. Discrete Math. 6 (1993), 214-229. Math. Review Link MR 95d:05043.
  5. A. CHANDRA, P. RAGHAVAN, W. RUSSO, R. SMOLENSKY AND P. TIWARI, The electrical resistance of a graph captures its commute and cover times, Comput. Complexity 6 (1996/97), 312-340. Math. Review Link MR 99h:60140.
  6. D. COPPERSMITH, P. TETALI AND P. WINKLER , Collisions Among Random Walks on a Graph, SIAM J. Discrete Math. 6 (1993), 363-374. Math. Review Link MR 94h:60103.
  7. R. DIESTEL, ``Graph Theory,'' Springer, New York, 1997. Math Review link not available.
  8. U. FEIGE, A Tight Upper Bound on the Cover Time for Random Walks on Graphs, Random Struct. Alg. 6 (1995), 51-54. Math. Review Link MR 97c:60174.
  9. U. FEIGE, A Tight Lower Bound on the Cover Time for Random Walks on Graphs, Random Struct. Alg. 6 (1995), 433-438. Math. Review Link MR 97c:60175.
  10. Z. HE AND O. SCHRAMM, Hyperbolic and Parabolic Packings, Discrete Comput. Geom. 14 (1995), 123-149. Math. Review Link MR 97i: 30009.
  11. J. KAHN, J. H. KIM, L. LOV´ASZ AND V. H. VU, The cover time, the blanket time, and the Matthews bound, Preprint (2000). Math Review link not available.
  12. P. KOEBE, Kontaktprobleme der konformen abbildung, Berichte Verhande. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Klasse 88 (1936) 141-164. Math Review link not available.
  13. S. MALITZ AND A. PAPAKOSTAS, On the angular resolution of planar graphs, SIAM J. Discrete Math., 7 (1994), 172-183. Math. Review Link MR 95c:05055.
  14. P. MATTHEWS, Covering Problems for Brownian Motion on Spheres, Ann. Probab. 16 (1988), 189-199. Math. Review Link MR 89a:60190.
  15. G. L. MILLER AND W. THURSTON, Separators in Two and three dimensions, in Proc. of the 22th Annual ACM Symposium on Theory of Computing, 300-309, Baltimore, (1990), ACM. Math Review link not available.
  16. B. RODIN AND D. SULLIVAN, The convergence of circle packings to the Riemann mapping, J. Differential Geom. 26 (1987), 349-360. Math. Review Link MR 90c:30007.
  17. D.A. SPIELMAN AND S.-H. TENG, Spectral partitioning works: planar graphs and finite element meshes, Proc. 37th Ann. Symp. Found. of Comp. Sci., IEEE (1996), 96-105. Math. Review Link MR 98d:65144.
  18. P. TETALI, Random walks and the effective resistance of networks, J. Theoret. Probab. 4 (1991) 101-109. Math. Review Link MR 92c:60097.
  19. D. ZUCKERMAN, Covering Times of Random Walks on Bounded-Degree Trees and Other Graphs, J. Theor. Probab. 2 (1989), 147-158. Math. Review Link MR 89m:60164.
  20. D. ZUCKERMAN, A technique for lower bounding the cover time, SIAM J. Disc. Math. 5 (1992), 81-87. Math. Review Link MR 93b:60155.
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X