Finding contracted vertices in a weighted directed graph Consider an edgeless graph $$g:=(V,E):=(\{1,2,\ldots,n\},\emptyset)$$ and an embedding of $g$ on the 2-dimensional Euclidean plane $\omega:V \rightarrow \mathbb{R}^2$.
Consider the surjection $$\phi:V \rightarrow V':\{1,2,\ldots,n\}\ \rightarrow \{1,2,\ldots,k\},$$ where $1 \leq k \leq n$, to be a relabelling of the vertices $V$ onto $V'$.
We say $c' \in V'$ is contracted if $|\phi^{-1}(c')|>1$, and those vertices $a,b,... \in V$ where $\phi(a) = \phi(b) = c'$, are called duplicates.
Let $l>0$, and call this our field of view diameter.
For every pair of vertices $u, v \in V$, if $u<v$ and $|\omega(v)-\omega(u)| \leq l$, construct the weighted directed edge as a 3-tuple:
$$(\phi(u), \phi(v), \omega(v)-\omega(u)),$$
consisting of two edge endpoints (the relabeled vertices $\phi(u)$ and $\phi(v)$), and an edge weight, which we set to be the difference vector $\omega(v)-\omega(u)$.
Calling the set of all such edges $E'$, we have constructed a weighted directed graph $g':=(V',E')$ which has $k$ vertices.
Problem: Given $l$ and $g'$, find $\phi$ and $\omega$.

(What follows is a more informal problem definition with examples and a more concrete motivating scenario)
Scenario: A finite subset of the natural numbers $1, 2, 3, ...$ is written in random locations on a wall.  A myopic observer looks very closely at small parts of the wall, measuring the relative distance between the midpoint of pairs of numbers no more than $l$ metres apart and nodes the distance x and y between pairs of numbers written on the wall.  That is, his field of view diameter is $l$.
From these measurements we can construct a directed graph $g' = (V',E')$, with each edge assigned weights $x$ and $y$.
(For example, suppose $l=3$, and numbers $45$ and $67$ are separated $1.5$ metres horizontally and $0.8$ metres vertically; in this case edge $(45, 67)$ is assigned the weights $x=1.5$ and $y=0.8$, since the Euclidean distance between $45$ and $67$ is just $|(1.5,0.8)| = sqrt(1.5^2 + 0.8^2) ~= 2.27 < 3$.)
Our myopic observer cannot see the whole wall at the same time, however, so he cannot be sure if any of the numbers farther than l apart from each other are duplicates.
Any pairs of duplicated numbers equal or closer than $l$ to each other will be trivial to identify since they will be recorded by the observer as self-loops.  So assume there are no duplicates separated by $l$ or less.
Problem: Knowing only $l$ and $g'$, how can we determine if there are any duplicated numbers on the wall, and if so, which ones?
That is, state a method for determining the subset $D$ of vertices $V'$ who appear more than once on the real wall, and for each vertex $v \in D$, a partition $P_v$ of the edges adjacent to $v$ corresponding to the real wall.
EXAMPLE 1
Suppose $l = 1.5$.  The wall and the induced graph shown below.  No duplicates; $D=\{\}$.

EXAMPLE 2
Suppose $l = 1.5$.  The wall and the induced graph shown below.  1 is duplicated.
$D=\{1\}$, $P_1 = \{\{(1,2)\},\{(3,1)\}\}$.

EXAMPLE 3
Suppose $l = 1.3$.  The wall and the induced graph shown below.  No duplicates; $D=\{\}$.

EXAMPLE 4
Suppose l = 1.3.  The wall and the induced graph shown below.  1 is duplicated.
$D=\{1\}$, $P_1 = \{\{(1,2)\},\{(5,1)\}\}$.

 A: This is more of an extended comment with gestures at what the answer might be and what the right question should be.

The first problem stated - find $\phi$ and $\omega$ - is not plausible to even imagine solving, because there's so many different possible vertex placements that result in the same data recorded in $g'$.
It is more reasonable to imagine trying to solve the second problem: can we determine if there are any duplicate numbers, and what they are?
Even this is not possible, because we can never rule out duplicate numbers. The two example diagrams below
1  2  3             1  2  3     3
      4  5                      4  5

produce the same weighted graph $g'$, even though the $3$ is duplicated in one of them.
A reasonable question is: given a weighted graph $g'$, is it possible that $g'$ comes from placing $k$ numbers with no duplicates?
This is solved by a simplified version of the "sum weights of edges of the cycle" algorithm. More precisely, if we assume there are no duplicates, then we can arbitrarily place one vertex at $(0,0)$ and use the weights to infer the placement of all other vertices. If this creates any contradictions (edges that aren't present but should be, or vice versa) then some numbers must have been duplicated.
If there are duplicates, it is not in general possible to identify which numbers are duplicated. The graph $g'$ in example 4 could come from either of the number placements below, as well as others:
1  2  3                 5  1  2  3
      4  5  1                    4  5

It's possible that we can still solve the following question: "What is the minimum number of duplicated vertices there could be?"
A: This problem is concerned with finding the inverse of a homeomorphism of graphs, namely the inverse of a quotient graph.
This problem appears to admit many solutions in the general case, and even in a restricted scenario, it is NP-complete.
https://www.sciencedirect.com/science/article/pii/S0166218X00002201?via%3Dihub
