algorithm - trapped inside a Graph : Find paths along edges that do not cross any edges

This is a graph based platformer level and the round shapes are creatures.

I am looking for a path traveling along edges that does not cross other edges(To simulate the creature crawling on the floors and walls).

Here is what the correct path would look like:

Answer

When traversing the graph, always turn the same direction. You can use cross product to check what is the left or rightmost direction in a junction.