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.
Best Answer
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.