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)$.
Best Answer
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:
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.)