Algorithm for enumerating all the faces of a multigraph with given planar embedding I am looking for an algorithm that enumerates all the faces of an unordered planar multigraph with a given planar embedding.
 A: To start, tag all the vertices with the letter $V$ to indicate that they are vertices of the original graph.
Now place two new vertices on every edge, every edge separates two faces. We are going to use tags on this vertices to keep track of the found faces.This new vertices are only for tagging purposes, when we talk about edges in the following steps we will be referring to the original ones. We will call the new vertices "tvertices"

Select a vertex tagged with $V$ and one of its edges. Tag the closest tvertex from the selected vertex with a $1$ to indicate that this one has been used for the first face.

From the selected vertex, swipe the selected edge clockwise until it meets another edge that emanates from the selected vertex. We select that edge and the other vertex that defines that edge. We now tag the tvertex of the new selected edge closest to the new selected vertex.

Continue swiping, reselecting and tagging until you get to the original vertex. The set of vertices and edges you had selected define a face.

Select now a vertex and one of its edges with the condition that the tvertex of said edge closest to the selected vertex has not been tagged yet. Repeat the same process to find a new face but now tagging the tvertices with $2$. Continue until all the tvertices have been tagged, changing the tag to $n+1$ once the $n$-th face has been found. 
All the faces have been found exactly once (this includes the exterior face).

