I may be missing a detail, but it seems to fail on a graph consisting of a loop with some extra edges branching off the loop toward its interior and some edges branching off toward the exterior. The left hand walk hits a dead end in one branch, and the right hand walk dead ends in the other, no matter where on the loop you start (except for some special cases).
Edit: strengthening the proposed counterexample
I think this is roughly the counterexample the person above was suggesting.
It's an edge case that should be handled, but does not prevent the general algo from working.
However, indeed it remains true that it does not find all loops, only the smallest set of loops that cover all edges.
you'd get the same pitfall of torus topology with 2 perpendicular loops
It sounds horribly slow, but isn't because the loop finding process for one edge can mark all edges it traverses as either being on the same loop, or not having a loop, for the orientation its checking. These edges can be skipped henceforth.
This does not find all loops, only the smallest disjoint loops (as every edge is at most part of two disjoint loops). But basically results in a similar planar "face" partition the author describes.
Its not clear to me whether my approach does not work (perhaps the angle compares fail on a torus? I've never had to deal with torii), or simply isn't suited because it misses some loops, but I thought I'd share it anyway :-)