On the Cover Time of Planar Graphs

By Johan Jonasson, Oded Schramm. 2000

54 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/868b0ea1071c18aad95990e0176fba047fd10875

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Computer Networks and Communications

Citations in the corpus

Geometric representations of graphs (2014, background): “Schramm [80] proved that every graph can be represented by a 3-polytope whose edges are tangent to a prescribed convex smooth body.”