---
res:
bibo_abstract:
- 'We present an efficient algorithm for a problem in the interface between clustering
and graph embeddings. An embedding '' : G ! M of a graph G into a 2manifold 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 '' : G ! M comes from an
embedding. A map '' : G ! M is a weak embedding if it can be perturbed into an
embedding ψ: G ! M with k'' "k < " for every " > 0. A polynomial-time
algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl
[14], which reduces to solving a system of linear equations over Z2. It runs in
O(n2!) O(n4:75) time, where 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 [14]: We perform a sequence
of local operations that gradually "untangles" the image ''(G) into
an embedding (G), or reports that '' 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 [1], and combines local constraints on the orientation of subgraphs
directly, thereby eliminating the need for solving large systems of linear equations.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Hugo
foaf_name: Akitaya, Hugo
foaf_surname: Akitaya
- foaf_Person:
foaf_givenName: Radoslav
foaf_name: Fulek, Radoslav
foaf_surname: Fulek
foaf_workInfoHomepage: http://www.librecat.org/personId=39F3FFE4-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0001-8485-1774
- foaf_Person:
foaf_givenName: Csaba
foaf_name: Tóth, Csaba
foaf_surname: Tóth
bibo_doi: 10.1137/1.9781611975031.20
dct_date: 2018^xs_gYear
dct_language: eng
dct_publisher: ACM@
dct_title: Recognizing weak embeddings of graphs@
...