Let's consider graphs of bounded degree.
I know that it's possible to detect cycles in a graph in linear time -- essentially do a depth-first search, depositing a trail along the path you're currently exploring and checking if there's an edge back to the trail.
I also know that it's possible to detect cycles in log-space: think of the edges at each vertex as being cyclically ordered, so there is a “successor edge” function (defined on directed edges corresponding to the undirected edges of the original graph) which maps $(u,v)$ to $(v,u')$, where $u'$ is next after $u$ among the neighbours of $v$; then loop over all directed edges $e$, and check if the first edge in the sequence $e$, $\mathrm{succ}(e)$, $\mathrm{succ}^2(e)$, ... whose target is the source of $e$ is different from the opposite of $e$. Note that this may require at least quadratic time, e.g. if the graph is a cycle of length $n$ with spikes added at each vertex and you're unlucky enough to start your exploration at the spikes.
Now my question: is it possible to detect cycles both in logspace and linear time?
In fact, I would even be happy if there were an algorithm using sublinear space, say $O(\sqrt n)$. I know probabilistic algorithms achieving runtime $O(\sqrt n)$, but no deterministic one.
