Recognizing Weak Embeddings of Graphs

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 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 ║φ – ψ ε ║ < ε for every ε > 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kynčl [14], which reduces to solving a system of linear equations over ℤ 2. It runs in O ( π 2 ω ) ≤ O ( n 4. 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.

Authors

• Hugo A. Akitaya
• Radoslav Fulek
• Csaba D. Tóth

Keywords

No keywords are indexed for this paper.