# How to identify named points by coordinates?

The problem: This is a reduced version of a problem I currently have. I have a list of edges as input. This list contains the names of 2 nodes (the edge connects these 2 nodes) and 2 x 2D coordinates (which is the start and the end of the edge). The nodes can be in an arbitrary order, and the whole list can contain duplicates. The wanted output is a list of each node (identified by name) and it's coordinates.

It can be assumed that the input uniquely identifies each point correctly, otherwise the algorithm can cancel with an error.

here is an example:

The input could be (AA,BB,CC are names of nodes)

AA,BB = (1,1),(2,2)
BB,AA = (2,2),(1,1)
BB,AA = (1,1),(2,2)
AA,CC = (1,1),(3,3)


The output would be :

AA = (1,1)
BB = (2,2)
CC = (3,3)


So essentially form a list of undirected edges, I want to fetch the list of named nodes.

My current solution: is a naive implementation, where I'm simple iterating (or recursing) through the input, I note 2 possible coordinates for each named node. If a coordinate verifies with another line of input I mark it as 'confirmed' and add it to the final result (and remove it from the set of 'possible' coordinates).

What I want: is a better solution, because this feels like a standard problem of graph theory. Can this be reduced to an existing problem, with an existing algorithm? I guess I'm overthinking this, and I all I need to do is putting the input in some kind of mathematical struct and the the solution is trivial or automatically there. Any ideas? Can this be reduced to a standard-problem? Is it possibly NP hard (so my naive implementation is the best I will find)? I'm also struggling to find a unique identifier, for a better solution. Is a name of a point uniquely identifying the 2D coordinate, or is the 2D coordinate uniquely identifying the named node? I have a bit of a blockage in my thinking and can't find a better way than my current one. I'm implementing it in Python, but if anyone has an idea (or hints) in plain words or pseudocode I'm happy to read them.

Thanks

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|)$.