Recognizing weak embeddings of graphs Conference Paper

Author(s): Akitaya, Hugo A; Fulek, Radoslav; Tóth, Csaba D
Title: Recognizing weak embeddings of graphs
Affiliation IST Austria
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.
Keywords: Polynomial approximation; Polynomial-time algorithms; Graph theory; MAtrix multiplication; Computational problem; Clustering algorithms; Data visualization; Linear equations; Maps; Corresponding vertices; Graph embeddings; Local constraints; Local operations; System of linear equations
Conference Title: 29th Annual ACM SIAM Symposium on Discrete Algorithms SODA 2018
Conference Dates: January 7 - 10, 2018
Conference Location: New Orleans, LA, USA
ISBN: 9781611975031
Publisher: ACM  
Date Published: 2018-01-01
Start Page: 274
End Page: 292
DOI: 10.1137/1.9781611975031.20
Notes: ∗Research supported in part by the NSF awards CCF-1422311 and CCF-1423615, and the Science Without Borders program. The second author gratefully acknowledges support from Austrian Science Fund (FWF): M2281-N35.
Open access: no
IST Austria Authors
  1. Radoslav Fulek
    14 Fulek
Related IST Austria Work