[Haskell-cafe] Navigating Graphs

Using something like zippers it is easy to navigate an acyclic graph in O(1) operations per arc you follow. Inspired by Chris Okasaki's work on queues I wondered if there is a similar approach to navigating cyclic graphs. If the graph you are navigating is static (i.e. does not have to support addition or removal of vertices in any reasonable amount of time), I guess you can get away with "Tying the know" (http://www.haskell.org/haskellwiki/Tying_the_Knot). But is there a technique that allows navigation, insertion and removal at focus in (at least amortised) O(1) operations each? As a generalisation being able to have multiple points of focus (in an acyclic graph for a start) would also be interesting. Any thoughts?