Recognizing weak embeddings of graphs

H. Akitaya, R. Fulek, C. Tóth, ACM Transactions on Algorithms 15 (2019) 50.


Journal Article | Published | English
Author
; ;
Department
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 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 ϕ : 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 ‖ ϕ − ψ ϵ ‖ < ϵ for every ϵ > 0, where ‖.‖ is the unform norm. A polynomial-time algorithm for recognizing weak embeddings has recently been found by Fulek and Kynčl. It reduces the problem to solving a system of linear equations over Z2. It runs in O(n2ω)≤ O(n4.75) time, where ω ∈ [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 local operations that gradually “untangles” the image ϕ(G) into an embedding ψ(G) or reports that ϕ 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.
Publishing Year
Date Published
2019-10-01
Journal Title
ACM Transactions on Algorithms
Volume
15
Issue
4
Article Number
50
IST-REx-ID

Cite this

Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 2019;15(4):50. doi:10.1145/3344549
Akitaya, H., Fulek, R., & Tóth, C. (2019). Recognizing weak embeddings of graphs. ACM Transactions on Algorithms, 15(4), 50. https://doi.org/10.1145/3344549
Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs.” ACM Transactions on Algorithms 15, no. 4 (2019): 50. https://doi.org/10.1145/3344549.
H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” ACM Transactions on Algorithms, vol. 15, no. 4, p. 50, 2019.
Akitaya H, Fulek R, Tóth C. 2019. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 15(4), 50.
Akitaya, Hugo, et al. “Recognizing Weak Embeddings of Graphs.” ACM Transactions on Algorithms, vol. 15, no. 4, ACM, 2019, p. 50, doi:10.1145/3344549.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1709.09209

Search this title in

Google Scholar