On the Cover Time of Planar Graphs

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.

• Publication year

  2000

• Venue

  Electronic Communications in Probability

• Publication date

  2000-02-04

• Fields of study

  Mathematics

• Identifiers
  DOI 10.1214/ECP.V5-1022arXiv math/0002034
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The cover time, the blanket time, and the Matthews bound

  2000cited by this paper
• Harmonic functions on planar and almost planar graphs and manifolds, via circle packings

  1996cited by this paper
• Spectral partitioning works: planar graphs and finite element meshes

  1996cited by this paper
• Hyperbolic and parabolic packings

  1995cited by this paper
• A Tight Lower Bound on the Cover Time for Random Walks on Graphs

  1995cited by this paper
• A Tight Upper Bound on the Cover Time for Random Walks on Graphs

  1995cited by this paper
• Collisions among Random Walks on a Graph

  1993cited by this paper
• Collisions Among Random Walks on a Graph

  1993influential reference
• Representations of Planar Graphs

  1993cited by this paper
• On the angular resolution of planar graphs

  1992cited by this paper
• Random walks and the effective resistance of networks

  1991cited by this paper
• A technique for lower bounding the cover time

  1990influential reference
• Separators in two and three dimensions

  1990cited by this paper
• The electrical resistance of a graph captures its commute and cover times

  1989cited by this paper
• Covering times of random walks on bounded degree trees and other graphs

  1989cited by this paper
• Covering Problems for Brownian Motion on Spheres

  1988cited by this paper
• The convergence of circle packings to the Riemann mapping

  1987cited by this paper
• On the time taken by random walks on finite groups to visit every state

  1983cited by this paper

• The rigidity of Doyle circle packings on the infinite hexagonal triangulation

  2024cites this paper
• Cover time of graphs with bounded genus

  2022cites this paper
• Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions

  2019cites this paper
• Graphs and Geometry

  2019cites this paper
• A Merge-Split Proposal for Reversible Monte Carlo Markov Chain Sampling of Redistricting Plans

  2019cites this paper
• Title Cover times for sequences of reversible Markov chains onrandom graphs

  2018cites this paper
• The Search Complexity of Collaborative Swarms in Expanding $$\mathbf{Z}^{2}$$ Grid Regions

  2018cites this paper
• How fast planar maps get swallowed by a peeling process

  2018cites this paper
• Planar Maps, Random Walks and Circle Packing

  2018influential citation
• Durham E-Theses Randomised Algorithms on Networks

  2016cites this paper
• UNIFORM SPANNING FORESTS OF PLANAR GRAPHS

  2016cites this paper
• A Brief Bibliography of Publications about the Kepler Conjecture

  2015cites this paper
• Loop-Erased Random Surfaces

  2015cites this paper
• Geometric representations of graphs

  2014cites this paper
• PR ] 2 9 Ju l 2 01 4 Exponential concentration of cover times

  2014cites this paper
• Exponential concentration of cover times

  2014cites this paper
• Traversals of Infinite Graphs with Random Local Orientations

  2013cites this paper
• Cover times for sequences of reversible Markov chains on random graphs

  2012cites this paper
• Simple random walks on wheel graphs

  2012cites this paper
• Decentralized Spatial Computing: Foundations of Geosensor Networks

  2012cites this paper
• TTLed Random Walks for Collaborative Monitoring in Mobile and Social Networks

  2012cites this paper
• Numerical evidence against a conjecture on the cover time of planar graphs.

  2011cites this paper
• Enhanced Random Walk with Choice: An Empirical Study

  2010cites this paper
• The Cover Time of Deterministic Random Walks

  2010influential citation
• Cover times, blanket times, and majorizing measures

  2010influential citation
• Coverage-maximization in networks under resource constraints.

  2010cites this paper
• Pure Topological Mapping in Mobile Robotics

  2010cites this paper
• Static and expanding grid coverage with ant robots: Complexity results

  2010cites this paper
• Efficient Collaborative Application Monitoring Scheme for Mobile Networks

  2010cites this paper
• Simple Random Walks on Radio Networks (Simple Random Walks on Hyper-Graphs)

  2009cites this paper
• Inferring environmental representations through limited sensory data with applications to sensor network self-calibration

  2009cites this paper
• Simple Random Walks on Radio Networks

  2009cites this paper
• On the Data Delivery Delay taken by Random Walks in Wireless Sensor Networks

  2008cites this paper
• Randomized protocols for information dissemination

  2008cites this paper
• PR ] 3 M ay 2 00 7 Many Random Walks Are Faster Than One

  2008cites this paper
• Analytical Evaluation of Unbiased Random Walks in Wireless Sensor Networks

  2008cites this paper
• Eigenvalues of graphs

  2007cites this paper
• On the cover time and mixing time of random geometric graphs

  2007cites this paper
• Many random walks are faster than one

  2007cites this paper
• Statistical Challenges with High Dimensionality: Feature Selection in Knowledge Discovery

  2006cites this paper
• The power of choice in random walks: an empirical study

  2006cites this paper
• Random geometric graphs: an algorithmic perspective

  2006cites this paper
• Simple random covering , disconnection , late and favorite points

  2006cites this paper
• Many Random Walks Are Faster Than One December

  2006cites this paper
• Favorite Points, Cover Times and Fractals

  2005cites this paper
• Learning Sensor Network Topology through Monte Carlo Expectation Maximization

  2005cites this paper
• On the Cover Time of Random Geometric Graphs

  2005cites this paper
• Learning Sensor Network Topology through Monte Carlo

  2005cites this paper
• A dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Computer Science

  2003cites this paper
• Cover times for Brownian motion and random walks in two dimensions

  2001cites this paper
• Unbiased Finite Planar Graphs are Asymptotically Recurrent

  2000cites this paper
• Recurrence of Distributional Limits of Finite Planar Graphs

  2000cites this paper
• Background Material

  year unknowncites this paper
• Non-commercial Research and Educational Use including without Limitation Use in Instruction at Your Institution, Sending It to Specific Colleagues That You Know, and Providing a Copy to Your Institution's Administrator. All Other Uses, Reproduction and Distribution, including without Limitation Comm

  year unknowncites this paper