Algorithm for generating a graph based on a planar graph? I have a planar embedding of a graph, $G(V,E)$.
The vertices, $V$, are points in $(x, y)$ space and the edges, $E$, are straight line segments from one vertex to another. Edges do not cross each other, by definition.
What I want to construct is a graph $X$ where the vertices refer to edges in $G$, and nodes in $X$ are adjacent if the corresponding edges in $G$ are adjacent to the face in $G$.
How would I go about constructing this graph given $G$? What would be the algorithm here? Is there a name/term to the kind of graph I am trying to make?
I believe my main bottleneck in figuring this out is that I don't know how to define a "face" properly. I know what a face looks like visually, but not mathematically/algorithmically.

Here's a visual example of what I mean:

The labels a-e refer to edges in $G$ and their corresponding vertices in $X$. The edges $a$ and $e$ are the only edges that aren't adjacent to a common face in $G$. There are only two faces in $G$: the infinite face and the finite one bounded by the triangle $(b, c, d)$.
 A: The graph $X$ you construct this way is the line graph of the dual graph of the original planar embedding.
To construct the graph, it's enough to be able to find faces: given an edge, to list the edges of the two faces on either side of that edge. Then we just do this for all edges to find $X$. How you do this depends on how you store the planar embedding as a data structure.
We might store a planar embedding by specifying the vertex coordinates. Here, the first step should be to sort the edges out of each vertex $v$ by the angle at which they exit $v$. This lets us find the "next edge clockwise out of $v$". Now, given an edge $vw$, we:


*

*Find the face on one side of $vw$ by taking the edge $wx$ that's next clockwise out of $w$, then taking the edge $xy$ that's next clockwise out of $x$, and so on until we get back to $vw$.

*Find the face on the other side of $vw$ by thinking of the edge as $wv$ and doing the same thing: taking the edge $vu$ that's next clockwise out of $v$, and so on until we get back to $wv$.


Knowing the faces incident to $vw$ tells us all the edges that share a face with $vw$. We can speed things up by remembering the edges on a face the first time we find it; then, when we look at other edges, if they are already in a face we've computed, we don't have to compute that face again.
A slightly more abstract way to store a planar embedding is as a doubly connected edge list. Here, for each edge (represented as a pair of half-edges $vw$ and $wv$) we simply remember the results of the operations we used in the algorithm above: $vw$ has a pointer to $\text{next}(vw)$ (the next edge clockwise out of $w$) and to $\text{twin}(vw)$ (the reverse edge $wv$). Otherwise, the method is the same.
(Half-edges in a DCEL structure also have a pointer to $\text{prev}(vw)$ for convenience: the half-edge $uv$ such that $\text{next}(uv) = vw$. We don't use that here, but it's useful in other situations.)
