[{"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","scopus_import":1,"author":[{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","full_name":"Filakovský, Marek","last_name":"Filakovský"},{"orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"id":"3AA52972-F248-11E8-B48F-1D18A9856A87","first_name":"Stephan Y","last_name":"Zhechev","full_name":"Zhechev, Stephan Y"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611975994.47"}],"publication_identifier":{"isbn":["9781611975994"]},"oa":1,"department":[{"_id":"UlWa"}],"date_created":"2020-05-10T22:00:48Z","language":[{"iso":"eng"}],"publication_status":"published","abstract":[{"text":"We consider the following decision problem EMBEDk→d in computational topology (where k ≤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd?\r\nThe special case EMBED1→2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are known to be decidable (as well as NP-hard), and recent results of Čadek et al. in computational homotopy theory, in combination with the classical Haefliger–Weber theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range .\r\nHere, by contrast, we prove that EMBEDk→d is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDk→d in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability.\r\nOur result complements (and in a wide range of dimensions strengthens) earlier results of Matoušek, Tancer, and the second author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ≥ 4.","lang":"eng"}],"volume":"2020-January","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"767-785","project":[{"_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF"}],"date_published":"2020-01-01T00:00:00Z","oa_version":"Published Version","year":"2020","date_updated":"2021-01-12T08:15:38Z","type":"conference","day":"01","publisher":"SIAM","status":"public","doi":"10.1137/1.9781611975994.47","article_processing_charge":"No","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2020-01-05","location":"Salt Lake City, UT, United States","end_date":"2020-01-08"},"citation":{"apa":"Filakovský, M., Wagner, U., &#38; Zhechev, S. Y. (2020). Embeddability of simplicial complexes is undecidable. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2020–January, pp. 767–785). Salt Lake City, UT, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611975994.47\">https://doi.org/10.1137/1.9781611975994.47</a>","ama":"Filakovský M, Wagner U, Zhechev SY. Embeddability of simplicial complexes is undecidable. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2020-January. SIAM; 2020:767-785. doi:<a href=\"https://doi.org/10.1137/1.9781611975994.47\">10.1137/1.9781611975994.47</a>","ista":"Filakovský M, Wagner U, Zhechev SY. 2020. Embeddability of simplicial complexes is undecidable. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 767–785.","chicago":"Filakovský, Marek, Uli Wagner, and Stephan Y Zhechev. “Embeddability of Simplicial Complexes Is Undecidable.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2020–January:767–85. SIAM, 2020. <a href=\"https://doi.org/10.1137/1.9781611975994.47\">https://doi.org/10.1137/1.9781611975994.47</a>.","short":"M. Filakovský, U. Wagner, S.Y. Zhechev, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785.","mla":"Filakovský, Marek, et al. “Embeddability of Simplicial Complexes Is Undecidable.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2020–January, SIAM, 2020, pp. 767–85, doi:<a href=\"https://doi.org/10.1137/1.9781611975994.47\">10.1137/1.9781611975994.47</a>.","ieee":"M. Filakovský, U. Wagner, and S. Y. Zhechev, “Embeddability of simplicial complexes is undecidable,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 767–785."},"_id":"7806","title":"Embeddability of simplicial complexes is undecidable","month":"01"},{"abstract":[{"lang":"eng","text":"In a straight-line embedded triangulation of a point set P in the plane, removing an inner edge and—provided the resulting quadrilateral is convex—adding the other diagonal is called an edge flip. The (edge) flip graph has all triangulations as vertices, and a pair of triangulations is adjacent if they can be obtained from each other by an edge flip. The goal of this paper is to contribute to a better understanding of the flip graph, with an emphasis on its connectivity.\r\nFor sets in general position, it is known that every triangulation allows at least edge flips (a tight bound) which gives the minimum degree of any flip graph for n points. We show that for every point set P in general position, the flip graph is at least -vertex connected. Somewhat more strongly, we show that the vertex connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P, provided P is large enough. Finally, we exhibit some of the geometry of the flip graph by showing that the flip graph can be covered by 1-skeletons of polytopes of dimension (products of associahedra).\r\nA corresponding result ((n – 3)-vertex connectedness) can be shown for the bistellar flip graph of partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. This will be treated separately in a second part."}],"volume":"2020-January","quality_controlled":"1","department":[{"_id":"UlWa"}],"external_id":{"arxiv":["2003.13557"]},"date_created":"2020-05-10T22:00:48Z","language":[{"iso":"eng"}],"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611975994.172"}],"oa":1,"publication_identifier":{"isbn":["9781611975994"]},"author":[{"orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"scopus_import":1,"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","article_processing_charge":"No","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2020-01-05","location":"Salt Lake City, UT, United States","end_date":"2020-01-08"},"citation":{"ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2020-January. SIAM; 2020:2823-2841. doi:<a href=\"https://doi.org/10.1137/1.9781611975994.172\">10.1137/1.9781611975994.172</a>","apa":"Wagner, U., &#38; Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2020–January, pp. 2823–2841). Salt Lake City, UT, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611975994.172\">https://doi.org/10.1137/1.9781611975994.172</a>","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2020–January:2823–41. SIAM, 2020. <a href=\"https://doi.org/10.1137/1.9781611975994.172\">https://doi.org/10.1137/1.9781611975994.172</a>.","ista":"Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841.","short":"U. Wagner, E. Welzl, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 2823–2841.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:<a href=\"https://doi.org/10.1137/1.9781611975994.172\">10.1137/1.9781611975994.172</a>.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part I: Edge flips),” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 2823–2841."},"related_material":{"record":[{"id":"12129","relation":"later_version","status":"public"}]},"_id":"7807","title":"Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)","month":"01","doi":"10.1137/1.9781611975994.172","arxiv":1,"type":"conference","publisher":"SIAM","day":"01","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"2823-2841","date_published":"2020-01-01T00:00:00Z","oa_version":"Submitted Version","year":"2020","date_updated":"2024-10-09T21:03:33Z"}]