  We present an efficient algorithm for a problem in the interface between
clustering and graph embeddings. An embedding $\varphi:G\rightarrow M$ of a
graph $G$ into a 2-manifold $M$ maps the vertices in $V(G)$ to distinct points
and the edges in $E(G)$ to interior-disjoint Jordan arcs between the
corresponding vertices. In applications in clustering, cartography, and
visualization, nearby vertices and edges are often bundled to the same point or
overlapping arcs, due to data compression or low resolution. This raises the
computational problem of deciding whether a given map $\varphi:G\rightarrow M$
comes from an embedding. A map $\varphi:G\rightarrow M$ is a \textbf{weak
embedding} if it can be perturbed into an embedding
$\psi_\varepsilon:G\rightarrow M$ with
$\|\varphi-\psi_\varepsilon\|<\varepsilon$ for every $\varepsilon>0$, where
$\|.\|$ is the unform norm. A polynomial-time algorithm for recognizing weak
embeddings has recently been found by Fulek and Kyn\v{c}l. It reduces the
problem to solving a system of linear equations over $\mathbb{Z}_2$. It runs in
$O(n^{2\omega})\leq O(n^{4.75})$ time, where $\omega\in [2,2.373)$ is the
matrix multiplication exponent and $n$ is the number of vertices and edges of
$G$. We improve the running time to $O(n\log n)$. Our algorithm is also
conceptually simpler: We perform a sequence of \emph{local operations} that
gradually "untangles" the image $\varphi(G)$ into an embedding $\psi(G)$, or
reports that $\varphi$ is not a weak embedding. It combines local constraints
on the orientation of subgraphs directly, thereby eliminating the need for
solving large systems of linear equations.
