Cover Time of Directed Graphs Given a random walk on a graph the cover time is the first time (expected number of steps) that every vertex has been hit (covered) by the walk. For connected undirected graphs, the cover time is known to be upper bounded by $O(n^3)$. There are strongly connected digraphs with cover time exponential in $n$. An example of this, is the digraph consisting of a directed cycle $(1, 2, ..., n, 1)$, and edges $(j, 1)$, from vertices $j = 2, ..., n − 1$. Starting from vertex $1$, the expected time for a random walk to reach vertex $n$ is $\Omega(2^n)$. I have two questions :

1) What are the known classes of directed graphs with polynomial cover time ? These classes might be characterized by graph-theoretic properties (or) by properties of the corresponding adjacency matrix (say $A$). For example, if $A$ is symmetric then cover time of the graph is polynomial.

2) Are there more simple examples (like the cycle example mentioned above) where the cover time is exponential ?

3) Are there examples with quasi-polynomial cover time ?

I would appreciate any pointers to good surveys/books on this topic.
Clearly polynomial mixing time implies polynomial cover time. (Well, not in general. We need the stationary probability at least $1/poly(n)$ at each vertex.) So check Mihail's paper Conductance and convergence of Markov chains-a combinatorial treatment of expanders which proves rapid mixing of regular directed graphs and general Markov chains based on conductance.

Also see the paper Pseudorandom walks on regular digraphs and the RL vs. L problem by Reingold, Trevisan, and Vadhan. Following Mihail's work. They defined the parameter $\lambda_\pi(G)$ which is equivalent to $\lambda_2(G)$, the second largest eigenvalue in absolute value, when the graph $G$ is time-reversible, and remains well-defined for general Markov chains. This parameter is then used to bound the mixing time of $G$.