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 $\bigl(1+o(1)\bigr)n\log n$ and at most $\bigl(1+o(1)\bigr)\frac{4}{27}n^3$. This paper proves that for bounded-degree planar graphs the cover time is at least $c n(\log n)^2$, and at most $6n^2$, 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: Download PDF | View PDF online (requires PDF plugin)

Pages: 85-90

Publication Date: May 5, 2000

DOI: 10.1214/ECP.v5-1022

References

  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.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.