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 a common node or arc , 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 weak embedding if it can be perturbed into an embedding \psi_\varepsilon:G\rightarrow M with \|\varphi-\psi_\varepsilon\|<\varepsilon for every \varepsilon> 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl , 2017 , which reduces to solving a system of linear equations over Z_2. It runs in O(n^{2\omega})\leq O(n^{4.75}) time, where \omega \approx  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 than Fulek and Kyn\v{c : 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 generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon Akitaya et al., 2016%DIFDELCMD < ]%%% , and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.
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 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 Kyncl . It reduces the problem to solving a system of linear equations over 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 %DIFDELCMD < ]%%% combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.
R
a common node or arc
the same point or overlapping arcs
R
weak embedding
weak embedding
R
0.
0, where \|.\| is the unform norm.
R
was recently found by
has recently been found by
D
, 2017
R
, which reduces
. It reduces the problem
R
\approx
\in
A
2,
A
)
D
than
D
Fulek and Kyn\v{c
D
generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon
D
Akitaya et al., 2016
D
, and