How to identify named points by coordinates?
I will assume the graph is connected (otherwise, break it down into connected components and recurse on each connected component).

Pick a single vertex.  Find an edge that uses that vertex.  That gives you two possibilities for the coordinates of that vertex.  Try one of them, propagate its implications, and see if it leads to a contradiction or a consistent assignment of coordinates to vertices. If it leads to a contradiction, try the other possibility.  If either leads to a consistent assignment, output that assignment.  If both lead to a contradiction, abort with an error.

So all that remains is to describe how to propagate the implications.  Suppose we have picked node AA and we assign it to location (2,2).  Then we find all edges between node AA and some other unassigned node.  This will let us assign a location to other other nodes, or abort with a cancellation.  For instance, once we assign AA to location (2,2), the edge AA,BB = (1,1),(2,2) causes us to assign BB to location (1,1) (which might trigger more implications) and the edge AA,CC = (1,1),(3,3) causes a contradiction (since AA can't be in location (2,2)).  Once this process completes, we check whether the resulting assignment is consistent with all of the edges; if not, we've found a contradiction.  Propagation can be done with any standard graph traversal algorithm, like DFS or BFS.

The running time to propagate the implications is linear in the size of the graph.  We only have to do that twice (once for each assumption about the location of the starting vertex), so the total running time is linear, i.e., $O(|V|+|E|)$.