See herehere for an algorithm. Consider each undirected edge as actually two edges, one going in each direction. Basically, if you order the edges around each vertex by angle, that will let you walk around each face in a clockwise direction, and you cross off each edge as you walk it. Then you pick and edge that hasn't been crossed off, and walk around starting with it.
However, since you're the one generating the graph, it might be easier just to generate the faces in the first place. When you get to a vertex on the edge of a map, take a left, and follow the outside edge by keeping taking the first right. Then branch off to the right and keep going around clockwise until you get back to the original vertex, taking care not to create a loop that doesn't include the original vertex. Then perhaps split the face once or twice.