After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work.
This problem reduces to finding all chordless cycles in a planar graph.
This was one of my first thoughts early on, but this doesn't work when you consider the following:
5-------f-------6
/ /|
/ / |
e g |
/ / h
/ / |
1-------a-------2 7
| | /
| | /
d b i
| | /
| |/
4-------c-------3
Given three sides, the answers should be: 1 2 3 4 1, 1 5 6 2 1, and 2 6 7 3 2. Unfortunately, 1 4 3 7 6 5 1 is considered chordless and is not a correct answer.
If you have vertices and edges - connect them. Adjacent edges will constitute a face.
Unfortunately, without weighting or accounting for spatial information you'll end up running into the edge cases described below.
Edge Cases
The highlighted "face" in the following two examples should not be in the solution. These highlighted faces are referred to as "internal faces" (yes, even the highlighted face on the right is considered an internal face in graphics terminology).
Then there are other issues like objects with distinct subgraphs, holes, and ambiguous face loops.
The Solution
While researching I found the paper: A new algorithm for finding faces in wireframes by Peter A. C. Varley and Pedro P. Company (full text here). The algorithm attempts to solve the problem for both 2D and 3D input. The solution is non-trivial: the setup alone is polynomial time.
Basic Description
Start by creating a set of directed edges from all edges of the graph (so the initial set is of size 2e were e is the number of edges). These sets of directed edges are stored as the vertices that comprise them and are referred to by the paper as "strings". Each string must be given a priority according to the geometry around it (e.g. there will be a different priority assigned depending upon if it touches a triangle or quadrilateral).
You then exhaustively attempt to merge the strings by finding ones that start were another one ends. You do this by picking the highest priority strings first.
When merging strings you remove the original strings from the set and add the merged version back in. When the merge is preformed a new priority must be calculated using the existing priorities and spatial information about the strings themselves (the spatial calculation differs depending upon if your running the algorithm against 2D or 3D input).
Strings are removed from the set if their first and last vertex match (that means a loop was found). You continue repeating the algorithm until the set is empty.
Complete Algorithm
Here is the complete algorithm copied directly from the paper. Hopefully the description I gave above helps a bit. The paper is very well written and its a good read for anyone interested in the topic.
Some steps in the algorithm come down to guesswork and assumptions about the input. For example, step #3 says to "choose a trihedral vertex", but if there is no trihedral vertices (e.g. octahedron or icosahedron) then the paper suggests breaking the symmetry by assuming that an arbitrary triangular loop of edges is a face.
(Top level of algorithm)
Create initial master string list, two entries per edge
Assign priorities to all strings in the list
Choose a trihedral vertex, and concatenate two strings at this vertex
While there are strings remaining in the master list
Examine the master list for the presence of forced concatenations
If there are forced concatenations, perform them
Otherwise, examine the master list for the presence of voluntary mergers
If there are voluntary mergers, perform them
Otherwise, examine hypotheses (see subroutine below)
(Subroutine: Examine Hypotheses)
Take a working copy of the master string list
Repeat
Take the highest-priority string S in the working string list
Find the string T which has the best mating value with S
Concatenate S and T, and reduce the priority of the resulting string
Repeat
Examine the working string list for the presence of a forced concatenation
If there is a forced concatenation, perform it
If the forced concatenation created a new face, update the master list accordingly and exit this subroutine
If there is no forced concatenation
If there is a voluntary merger available, create the face, update the master list accordingly and exit this subroutine
Otherwise exit this inner loop
Other Solutions
According to the paper, the current face-finding algorithms generally fall into four categories: exhaustive search approaches, pseudo-random approaches,
shortest-path approaches, and heavily mathematical approaches. It does a good job citing other possible solutions along with their advantages and disadvantages.
Keep in mind that this algorithm acknowledges that it still produces incorrect output for certain input. However, this is still an improvement over the previous best solution which fails for even more input.
