Find all faces in a graph from list of edges I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 shares edges with nodes 1 8 and 30. As the graph is undirected, graph[8] will also contain the value 3.
I want to find an algorithm that will find all of the faces of the graph (my graph-theoretical knowledge is limited, I am essentially looking for all of the cycles that don't contain a smaller cycle within them), and provide the path for the boundary of each of those faces (e.g. 1->5->9->3->1).
It is safe to assume that the graph I have is both planar and connected.
With limited knowledge of graph-theory concepts I'd like to avoid getting too lost halfway through implementation, so simplicity is probably more valuable than efficiency. That said, the algorithm must not be horribly inefficient.
 A: Expanding a bit on the comments to Federico's answer: If the neighbors of each vertex are listed in counterclockwise order, this defines an embedding on a surface, and if this information was obtained from a given planar embedding, this is the one you get back. 
Essentially, for a given edge $(n_1,n_2)$ you can find one of the faces it borders (and, analogously, the other one by considering $(n_2,n_1)$ instead) by looking up $n_1$ in the list of $n_2$'s neighbors, finding the next one, say $n_3$, in the (cyclic) order, and continuing with $(n_2,n_3)$, and then $(n_3,n_4)$ etc until you return to $n_1$. 
Note that the non-uniqueness is only an issue if $G$ is not $3$-edge-connected. If it is, even if the ordering at the nodes is not given, you should still have a unique embedding into the sphere (and into the plane, modulo choice of the outer face). Not sure how to find it, though.
A: What you ask for is an unsolvable problem, because it depends on the embedding of the graph in the plane (or space). Consider the following graphs:
          

They are isomorphic, and described by the same node-edge incidence matrix, but you want different answers for them.
You need to specify a planar embedding (i.e., coordinates for the vertices) for this to work.
