--- _id: '309' abstract: - lang: eng text: '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.' acknowledgement: '∗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.' article_processing_charge: No author: - first_name: Hugo full_name: Akitaya, Hugo last_name: Akitaya - first_name: Radoslav full_name: Fulek, Radoslav id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87 last_name: Fulek orcid: 0000-0001-8485-1774 - first_name: Csaba full_name: Tóth, Csaba last_name: Tóth citation: ama: 'Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. In: ACM; 2018:274-292. doi:10.1137/1.9781611975031.20' apa: 'Akitaya, H., Fulek, R., & Tóth, C. (2018). Recognizing weak embeddings of graphs (pp. 274–292). Presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA: ACM. https://doi.org/10.1137/1.9781611975031.20' chicago: Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs,” 274–92. ACM, 2018. https://doi.org/10.1137/1.9781611975031.20. ieee: 'H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA, 2018, pp. 274–292.' ista: 'Akitaya H, Fulek R, Tóth C. 2018. Recognizing weak embeddings of graphs. SODA: Symposium on Discrete Algorithms, 274–292.' mla: Akitaya, Hugo, et al. Recognizing Weak Embeddings of Graphs. ACM, 2018, pp. 274–92, doi:10.1137/1.9781611975031.20. short: H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292. conference: end_date: 2018-01-10 location: New Orleans, LA, USA name: 'SODA: Symposium on Discrete Algorithms' start_date: 2018-01-07 date_created: 2018-12-11T11:45:45Z date_published: 2018-01-01T00:00:00Z date_updated: 2023-09-15T12:19:32Z day: '01' department: - _id: UlWa doi: 10.1137/1.9781611975031.20 external_id: arxiv: - '1709.09209' isi: - '000483921200021' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1709.09209 month: '01' oa: 1 oa_version: Preprint page: 274 - 292 project: - _id: 261FA626-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02281 name: Eliminating intersections in drawings of graphs publication_status: published publisher: ACM publist_id: '7556' quality_controlled: '1' related_material: record: - id: '6982' relation: later_version status: public scopus_import: '1' status: public title: Recognizing weak embeddings of graphs type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2018' ...