If you have seen my last question: trapped inside a Graph : Find paths along edges that do not cross any edges

How do you split an entire graph into distinct shapes 'trapped' inside the graph(like the ones described in my last question) with good complexity?

What I am doing now is iterating over all edges and then starting to traverse while always taking the rightmost turn. This does split the graph into distinct shapes. Then I eliminate all the excess shapes (that are repeats of previous shapes) and return the result.

The complexity of this algorithm is O(E^2). I am wondering if I could do it in O(E) by removing edges I already traversed previously. My current implementation of that returns unexpected results.