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.