I am assuming the graph is a planar graph. This method will not work for a planar embedding of a nonplanar graph. Every edge is adjacent to exactly two faces. Given a single edge of a bounded face, it will be traversed by in its adjacent face. So, turn it into a binary vector space. Let . After adding all face cycles together, whatever is left is guaranteed to be the face cycle of the unbounded cycle (just traversed in the opposite direction).