{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T04:09:51Z","timestamp":1780891791832,"version":"3.54.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T00:00:00Z","timestamp":1570147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-142231, CCF-1423615"],"award-info":[{"award-number":["CCF-142231, CCF-1423615"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Austrian Science Fund","award":["M2281-N35"],"award-info":[{"award-number":["M2281-N35"]}]},{"DOI":"10.13039\/501100017564","name":"Science Without Borders","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100017564","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"\n We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An\n embedding<\/jats:bold>\n \u03c6 :\n G<\/jats:italic>\n \u2192\n M<\/jats:italic>\n of a graph\n G<\/jats:italic>\n into a 2-manifold\n M<\/jats:italic>\n maps the vertices in\n V<\/jats:italic>\n (\n G<\/jats:italic>\n ) to distinct points and the edges in\n E<\/jats:italic>\n (\n G<\/jats:italic>\n ) 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 \u03c6 :\n G<\/jats:italic>\n \u2192\n M<\/jats:italic>\n comes from an embedding. A map \u03c6 :\n G<\/jats:italic>\n \u2192\n M<\/jats:italic>\n is a\n weak embedding<\/jats:bold>\n if it can be perturbed into an embedding \u03c8\n \u03b5<\/jats:sub>\n :\n G<\/jats:italic>\n \u2192\n M<\/jats:italic>\n with \u2016 \u03c6 \u2212 \u03c8\n \u03b5<\/jats:sub>\n \u2016 < \u03b5 for every \u03b5 > 0, where \u2016.\u2016 is the unform norm.\n <\/jats:p>\n \n A polynomial-time algorithm for recognizing weak embeddings has recently been found by Fulek and Kyn\u010dl. It reduces the problem to solving a system of linear equations over Z\n 2<\/jats:sub>\n . It runs in\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 2\u03c9<\/jats:sup>\n )\u2264\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 4.75<\/jats:sup>\n ) time, where \u03c9 \u2208 [2,2.373) is the matrix multiplication exponent and\n n<\/jats:italic>\n is the number of vertices and edges of\n G<\/jats:italic>\n . We improve the running time to\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n ). Our algorithm is also conceptually simpler: We perform a sequence of\n local operations<\/jats:italic>\n that gradually \u201cuntangles\u201d the image \u03c6(\n G<\/jats:italic>\n ) into an embedding \u03c8(\n G<\/jats:italic>\n ) or reports that \u03c6 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.\n <\/jats:p>","DOI":"10.1145\/3344549","type":"journal-article","created":{"date-parts":[[2019,10,7]],"date-time":"2019-10-07T12:20:59Z","timestamp":1570450859000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Recognizing Weak Embeddings of Graphs"],"prefix":"10.1145","volume":"15","author":[{"given":"Hugo A.","family":"Akitaya","sequence":"first","affiliation":[{"name":"Tufts University, Medford, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8485-1774","authenticated-orcid":false,"given":"Radoslav","family":"Fulek","sequence":"additional","affiliation":[{"name":"Institute of Science and Technology, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8769-3190","authenticated-orcid":false,"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[{"name":"California State University Northridge, Tufts University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9918-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-00541-w"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0128-9"},{"key":"e_1_2_1_4_1","first-page":"802","article-title":"Self-nonintersecting and non intersecting chains","volume":"34","author":"Belyi S. B.","year":"1983","unstructured":"S. B. Belyi . 1983 . Self-nonintersecting and non intersecting chains . Math. Notes Acad. Sci. USSR 34 , 4 (1983), 802 -- 804 . DOI:https:\/\/doi.org\/10.1007\/BF01157400 Translated from Matematicheskie Zametki, Vol. 34, No. 4, pp. 625--628, 1983. 10.1007\/BF01157400 S. B. Belyi. 1983. Self-nonintersecting and non intersecting chains. Math. Notes Acad. Sci. USSR 34, 4 (1983), 802--804. DOI:https:\/\/doi.org\/10.1007\/BF01157400 Translated from Matematicheskie Zametki, Vol. 34, No. 4, pp. 625--628, 1983.","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.03.005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.110"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.090"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04414-5_2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.86"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794280736"},{"key":"e_1_2_1_11_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2017. Graph Theory ( 5 th ed.). Graduate Texts in Mathematics, Vol. 173 . Springer , Heidelberg. Reinhard Diestel. 2017. Graph Theory (5th ed.). Graduate Texts in Mathematics, Vol. 173. Springer, Heidelberg.","edition":"5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0030816"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/647905.739634"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Yoshio Okamoto and Takeshi Tokuyama (Eds.)","volume":"92","author":"Fulek Radoslav","year":"2017","unstructured":"Radoslav Fulek . 2017 . Embedding graphs into embedded graphs . In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Yoshio Okamoto and Takeshi Tokuyama (Eds.) , Vol. 92 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 34:1--34:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC. 2017.34 10.4230\/LIPIcs.ISAAC.2017.34 Radoslav Fulek. 2017. Embedding graphs into embedded graphs. In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Yoshio Okamoto and Takeshi Tokuyama (Eds.), Vol. 92. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 34:1--34:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.34"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 34th Symposium on Computational Geometry (LiPICS)","volume":"99","author":"Fulek Radoslav","year":"2018","unstructured":"Radoslav Fulek and Jan Kyn\u010dl . 2018 . Hanani-Tutte for approximating maps of graphs . In Proceedings of the 34th Symposium on Computational Geometry (LiPICS) , Vol. 99 . Schloss Dagstuhl. Retrieved from: arXiv:1705.05243. Radoslav Fulek and Jan Kyn\u010dl. 2018. Hanani-Tutte for approximating maps of graphs. In Proceedings of the 34th Symposium on Computational Geometry (LiPICS), Vol. 99. Schloss Dagstuhl. Retrieved from: arXiv:1705.05243."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-23-1-135-142"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-37623-2_17"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-8641(97)00121-1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-65-3-325-343"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02305012"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-8641(03)00069-5"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90006-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80007-2"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 44th Symposium on Theory of Computing (STOC\u201912)","author":"Williams Virginia Vassilevska","year":"2012","unstructured":"Virginia Vassilevska Williams . 2012 . Multiplying matrices faster than Coppersmith-Winograd [extended abstract] . In Proceedings of the 44th Symposium on Theory of Computing (STOC\u201912) . ACM Press, New York, NY, 887--898. DOI:https:\/\/doi.org\/10.1145\/2213977.2214056 10.1145\/2213977.2214056 Virginia Vassilevska Williams. 2012. Multiplying matrices faster than Coppersmith-Winograd [extended abstract]. In Proceedings of the 44th Symposium on Theory of Computing (STOC\u201912). ACM Press, New York, NY, 887--898. DOI:https:\/\/doi.org\/10.1145\/2213977.2214056"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344549","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3344549","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3344549","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:25Z","timestamp":1750203865000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344549"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,4]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3344549"],"URL":"https:\/\/doi.org\/10.1145\/3344549","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,4]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}