[{"date_created":"2019-11-26T10:13:59Z","_id":"7108","date_published":"2019-06-01T00:00:00Z","scopus_import":"1","related_material":{"record":[{"id":"184","relation":"earlier_version","status":"public"}]},"abstract":[{"text":"We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.","lang":"eng"}],"author":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"full_name":"Patak, Pavel","first_name":"Pavel","last_name":"Patak","id":"B593B804-1035-11EA-B4F1-947645A5BB83"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova","orcid":"0000-0002-3975-1683","first_name":"Zuzana","full_name":"Patakova, Zuzana"},{"last_name":"Tancer","first_name":"Martin","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"issue":"3","arxiv":1,"type":"journal_article","date_updated":"2023-09-06T11:10:58Z","publication_status":"published","intvolume":"        66","month":"06","language":[{"iso":"eng"}],"doi":"10.1145/3314024","year":"2019","volume":66,"oa_version":"Preprint","article_type":"original","main_file_link":[{"open_access":"1","url":"https://arxiv.org/pdf/1711.08436.pdf"}],"article_number":"21","day":"01","oa":1,"citation":{"ama":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. <i>Journal of the ACM</i>. 2019;66(3). doi:<a href=\"https://doi.org/10.1145/3314024\">10.1145/3314024</a>","mla":"Goaoc, Xavier, et al. “Shellability Is NP-Complete.” <i>Journal of the ACM</i>, vol. 66, no. 3, 21, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3314024\">10.1145/3314024</a>.","apa":"Goaoc, X., Patak, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2019). Shellability is NP-complete. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3314024\">https://doi.org/10.1145/3314024</a>","ista":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete. Journal of the ACM. 66(3), 21.","short":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM 66 (2019).","ieee":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” <i>Journal of the ACM</i>, vol. 66, no. 3. ACM, 2019.","chicago":"Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete.” <i>Journal of the ACM</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3314024\">https://doi.org/10.1145/3314024</a>."},"isi":1,"quality_controlled":"1","publication_identifier":{"issn":["0004-5411"]},"publisher":"ACM","status":"public","title":"Shellability is NP-complete","department":[{"_id":"UlWa"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication":"Journal of the ACM","article_processing_charge":"No","external_id":{"arxiv":["1711.08436"],"isi":["000495406300007"]}},{"intvolume":"     11904","publication_status":"published","date_updated":"2023-09-06T14:56:00Z","type":"conference","arxiv":1,"year":"2019","doi":"10.1007/978-3-030-35802-0_18","month":"11","language":[{"iso":"eng"}],"scopus_import":"1","date_published":"2019-11-28T00:00:00Z","date_created":"2020-01-05T23:00:47Z","conference":{"name":"GD: Graph Drawing and Network Visualization","end_date":"2019-09-20","start_date":"2019-09-17","location":"Prague, Czech Republic"},"_id":"7230","author":[{"full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","last_name":"Arroyo Guevara","first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Derka, Martin","first_name":"Martin","last_name":"Derka"},{"full_name":"Parada, Irene","last_name":"Parada","first_name":"Irene"}],"abstract":[{"text":"Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. In this paper we study the problem of extending a simple drawing D(G) of a graph G by inserting a set of edges from the complement of G into D(G) such that the result is a simple drawing. In the context of rectilinear drawings, the problem is trivial. For pseudolinear drawings, the existence of such an extension follows from Levi’s enlargement lemma. In contrast, we prove that deciding if a given set of edges can be inserted into a simple drawing is NP-complete. Moreover, we show that the maximization version of the problem is APX-hard. We also present a polynomial-time algorithm for deciding whether one edge uv can be inserted into D(G) when {u,v} is a dominating set for the graph G.","lang":"eng"}],"ec_funded":1,"department":[{"_id":"UlWa"}],"status":"public","title":"Extending simple drawings","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer Nature","external_id":{"isi":["000612918800018"],"arxiv":["1908.08129"]},"project":[{"grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"publication":"27th International Symposium on Graph Drawing and Network Visualization","article_processing_charge":"No","alternative_title":["LNCS"],"main_file_link":[{"url":"https://arxiv.org/abs/1908.08129","open_access":"1"}],"page":"230-243","oa_version":"Preprint","volume":11904,"quality_controlled":"1","isi":1,"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["978-3-0303-5801-3"]},"day":"28","citation":{"short":"A.M. Arroyo Guevara, M. Derka, I. Parada, in:, 27th International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2019, pp. 230–243.","chicago":"Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple Drawings.” In <i>27th International Symposium on Graph Drawing and Network Visualization</i>, 11904:230–43. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">https://doi.org/10.1007/978-3-030-35802-0_18</a>.","ieee":"A. M. Arroyo Guevara, M. Derka, and I. Parada, “Extending simple drawings,” in <i>27th International Symposium on Graph Drawing and Network Visualization</i>, Prague, Czech Republic, 2019, vol. 11904, pp. 230–243.","ama":"Arroyo Guevara AM, Derka M, Parada I. Extending simple drawings. In: <i>27th International Symposium on Graph Drawing and Network Visualization</i>. Vol 11904. Springer Nature; 2019:230-243. doi:<a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">10.1007/978-3-030-35802-0_18</a>","mla":"Arroyo Guevara, Alan M., et al. “Extending Simple Drawings.” <i>27th International Symposium on Graph Drawing and Network Visualization</i>, vol. 11904, Springer Nature, 2019, pp. 230–43, doi:<a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">10.1007/978-3-030-35802-0_18</a>.","apa":"Arroyo Guevara, A. M., Derka, M., &#38; Parada, I. (2019). Extending simple drawings. In <i>27th International Symposium on Graph Drawing and Network Visualization</i> (Vol. 11904, pp. 230–243). Prague, Czech Republic: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">https://doi.org/10.1007/978-3-030-35802-0_18</a>","ista":"Arroyo Guevara AM, Derka M, Parada I. 2019. Extending simple drawings. 27th International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 11904, 230–243."},"oa":1},{"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","first_name":"Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek"},{"first_name":"Jan","last_name":"Kyncl","full_name":"Kyncl, Jan"}],"abstract":[{"text":"The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. ","lang":"eng"}],"scopus_import":1,"date_published":"2019-06-01T00:00:00Z","conference":{"location":"Portland, OR, United States","start_date":"2019-06-18","end_date":"2019-06-21","name":"SoCG: Symposium on Computational Geometry"},"_id":"7401","date_created":"2020-01-29T16:17:05Z","ddc":["000"],"year":"2019","doi":"10.4230/LIPICS.SOCG.2019.39","language":[{"iso":"eng"}],"month":"06","intvolume":"       129","publication_status":"published","date_updated":"2021-01-12T08:13:24Z","arxiv":1,"type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"quality_controlled":"1","citation":{"ieee":"R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric matrices,” in <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>, Portland, OR, United States, 2019, vol. 129.","chicago":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” In <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>, Vol. 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">https://doi.org/10.4230/LIPICS.SOCG.2019.39</a>.","short":"R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","ista":"Fulek R, Kyncl J. 2019. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. 35th International Symposium on Computational Geometry (SoCG 2019). SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 39.","apa":"Fulek, R., &#38; Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In <i>35th International Symposium on Computational Geometry (SoCG 2019)</i> (Vol. 129). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">https://doi.org/10.4230/LIPICS.SOCG.2019.39</a>","ama":"Fulek R, Kyncl J. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In: <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">10.4230/LIPICS.SOCG.2019.39</a>","mla":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>, vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">10.4230/LIPICS.SOCG.2019.39</a>."},"oa":1,"day":"01","article_number":"39","alternative_title":["LIPIcs"],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"oa_version":"Published Version","volume":129,"file":[{"file_size":628347,"relation":"main_file","content_type":"application/pdf","file_name":"2019_LIPIcs_Fulek.pdf","file_id":"7445","creator":"dernst","date_created":"2020-02-04T09:14:31Z","date_updated":"2020-07-14T12:47:57Z","checksum":"aac37b09118cc0ab58cf77129e691f8c","access_level":"open_access"}],"project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1903.08637"]},"article_processing_charge":"No","publication":"35th International Symposium on Computational Geometry (SoCG 2019)","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:57Z","title":"Z_2-Genus of graphs and minimum rank of partial symmetric matrices","status":"public","department":[{"_id":"UlWa"}],"has_accepted_license":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"Extending partial representations of circle graphs","status":"public","department":[{"_id":"UlWa"}],"publisher":"Wiley","project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1309.2399"],"isi":["000485392800004"]},"article_processing_charge":"No","publication":"Journal of Graph Theory","main_file_link":[{"url":"https://arxiv.org/abs/1309.2399","open_access":"1"}],"page":"365-394","volume":91,"oa_version":"Preprint","article_type":"original","publication_identifier":{"issn":["03649024"]},"isi":1,"quality_controlled":"1","oa":1,"citation":{"chicago":"Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>. Wiley, 2019. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>.","ieee":"S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” <i>Journal of Graph Theory</i>, vol. 91, no. 4. Wiley, pp. 365–394, 2019.","short":"S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.","ista":"Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394.","apa":"Chaplick, S., Fulek, R., &#38; Klavík, P. (2019). Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>","ama":"Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. 2019;91(4):365-394. doi:<a href=\"https://doi.org/10.1002/jgt.22436\">10.1002/jgt.22436</a>","mla":"Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:<a href=\"https://doi.org/10.1002/jgt.22436\">10.1002/jgt.22436</a>."},"day":"01","publication_status":"published","intvolume":"        91","arxiv":1,"type":"journal_article","date_updated":"2023-08-24T14:30:43Z","doi":"10.1002/jgt.22436","year":"2019","language":[{"iso":"eng"}],"month":"08","date_published":"2019-08-01T00:00:00Z","scopus_import":"1","_id":"5790","date_created":"2018-12-30T22:59:15Z","issue":"4","abstract":[{"text":"The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest.","lang":"eng"}],"author":[{"full_name":"Chaplick, Steven","first_name":"Steven","last_name":"Chaplick"},{"first_name":"Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klavík, Pavel","last_name":"Klavík","first_name":"Pavel"}],"ec_funded":1},{"publication_status":"published","intvolume":"       259","type":"journal_article","arxiv":1,"date_updated":"2023-08-24T14:39:33Z","doi":"10.1016/j.dam.2018.12.025","year":"2019","language":[{"iso":"eng"}],"month":"04","date_published":"2019-04-30T00:00:00Z","scopus_import":"1","_id":"5857","date_created":"2019-01-20T22:59:17Z","issue":"4","author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"János","last_name":"Pach","full_name":"Pach, János"}],"abstract":[{"text":"A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1), and that this bound is best possible for infinitely many values of n.","lang":"eng"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"433"}]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"Thrackles: An improved upper bound","department":[{"_id":"UlWa"}],"status":"public","publisher":"Elsevier","project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1708.08037"],"isi":["000466061100020"]},"article_processing_charge":"No","publication":"Discrete Applied Mathematics","main_file_link":[{"url":"https://arxiv.org/abs/1708.08037","open_access":"1"}],"oa_version":"Preprint","volume":259,"page":"266-231","article_type":"original","publication_identifier":{"issn":["0166218X"]},"isi":1,"quality_controlled":"1","oa":1,"citation":{"apa":"Fulek, R., &#38; Pach, J. (2019). Thrackles: An improved upper bound. <i>Discrete Applied Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">https://doi.org/10.1016/j.dam.2018.12.025</a>","ama":"Fulek R, Pach J. Thrackles: An improved upper bound. <i>Discrete Applied Mathematics</i>. 2019;259(4):266-231. doi:<a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">10.1016/j.dam.2018.12.025</a>","mla":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” <i>Discrete Applied Mathematics</i>, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:<a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">10.1016/j.dam.2018.12.025</a>.","ista":"Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics. 259(4), 266–231.","short":"R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” <i>Discrete Applied Mathematics</i>, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” <i>Discrete Applied Mathematics</i>. Elsevier, 2019. <a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">https://doi.org/10.1016/j.dam.2018.12.025</a>."},"day":"30"},{"scopus_import":"1","date_published":"2019-06-01T00:00:00Z","date_created":"2019-02-14T11:54:08Z","_id":"5986","author":[{"last_name":"Lubiw","first_name":"Anna","full_name":"Lubiw, Anna"},{"full_name":"Masárová, Zuzana","first_name":"Zuzana","last_name":"Masárová","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"lang":"eng","text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture."}],"issue":"4","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"683"},{"relation":"dissertation_contains","status":"public","id":"7944"}]},"intvolume":"        61","publication_status":"published","date_updated":"2023-09-07T13:17:36Z","type":"journal_article","arxiv":1,"year":"2019","doi":"10.1007/s00454-018-0035-8","ddc":["000"],"month":"06","language":[{"iso":"eng"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"file":[{"date_created":"2019-02-14T11:57:22Z","date_updated":"2020-07-14T12:47:14Z","access_level":"open_access","checksum":"e1bff88f1d77001b53b78c485ce048d7","file_size":556276,"content_type":"application/pdf","relation":"main_file","file_name":"2018_DiscreteGeometry_Lubiw.pdf","creator":"dernst","file_id":"5988"}],"article_type":"original","oa_version":"Published Version","volume":61,"page":"880-898","quality_controlled":"1","isi":1,"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"day":"01","citation":{"ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. 2019;61(4):880-898. doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>","mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>.","apa":"Lubiw, A., Masárová, Z., &#38; Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>","ista":"Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete &#38; Computational Geometry. 61(4), 880–898.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete &#38; Computational Geometry 61 (2019) 880–898.","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>."},"oa":1,"department":[{"_id":"UlWa"}],"title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","status":"public","has_accepted_license":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file_date_updated":"2020-07-14T12:47:14Z","publisher":"Springer Nature","external_id":{"arxiv":["1710.02741"],"isi":["000466130000009"]},"project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"publication":"Discrete & Computational Geometry","article_processing_charge":"Yes (via OA deal)"},{"month":"06","language":[{"iso":"eng"}],"year":"2019","doi":"10.4230/LIPIcs.SoCG.2019.44","ddc":["516"],"date_updated":"2023-09-07T13:18:26Z","arxiv":1,"type":"conference","keyword":["computational 3-manifold topology","fixed-parameter tractability","layered triangulations","structural graph theory","treewidth","cutwidth","Heegaard genus"],"intvolume":"       129","publication_status":"published","related_material":{"record":[{"id":"8032","relation":"part_of_dissertation","status":"public"}]},"abstract":[{"text":"Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.","lang":"eng"}],"author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár","orcid":"0000-0002-5445-5057","first_name":"Kristóf","full_name":"Huszár, Kristóf"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"}],"date_created":"2019-06-11T20:09:57Z","_id":"6556","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2019-06-21","location":"Portland, Oregon, United States","start_date":"2019-06-18"},"scopus_import":"1","date_published":"2019-06-01T00:00:00Z","publication":"35th International Symposium on Computational Geometry","article_processing_charge":"No","external_id":{"arxiv":["1812.05528"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","status":"public","title":"3-manifold triangulations with small treewidth","department":[{"_id":"UlWa"}],"has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:33Z","day":"01","citation":{"ama":"Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: <i>35th International Symposium on Computational Geometry</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">10.4230/LIPIcs.SoCG.2019.44</a>","mla":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” <i>35th International Symposium on Computational Geometry</i>, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">10.4230/LIPIcs.SoCG.2019.44</a>.","apa":"Huszár, K., &#38; Spreer, J. (2019). 3-manifold triangulations with small treewidth. In <i>35th International Symposium on Computational Geometry</i> (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>","ista":"Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.","short":"K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.","chicago":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In <i>35th International Symposium on Computational Geometry</i>, 129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2019.44\">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>.","ieee":"K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in <i>35th International Symposium on Computational Geometry</i>, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20."},"oa":1,"quality_controlled":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"file":[{"relation":"main_file","content_type":"application/pdf","file_name":"2019_LIPIcs-Huszar.pdf","creator":"kschuh","file_id":"6557","file_size":905885,"access_level":"open_access","checksum":"29d18c435368468aa85823dabb157e43","date_created":"2019-06-12T06:45:33Z","date_updated":"2020-07-14T12:47:33Z"}],"page":"44:1-44:20","volume":129,"oa_version":"Published Version","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"alternative_title":["LIPIcs"]},{"scopus_import":1,"date_published":"2018-06-01T00:00:00Z","date_created":"2018-12-11T11:45:37Z","_id":"285","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2018-06-14","location":"Budapest, Hungary","start_date":"2018-06-11"},"abstract":[{"lang":"eng","text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how &quot;simple&quot; or &quot;thin&quot; a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1))."}],"author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","full_name":"Huszár, Kristóf","first_name":"Kristóf","orcid":"0000-0002-5445-5057","last_name":"Huszár"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"},{"full_name":"Wagner, Uli","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"id":"7093","status":"public","relation":"later_version"}]},"intvolume":"        99","publication_status":"published","date_updated":"2023-09-06T11:13:41Z","type":"conference","arxiv":1,"year":"2018","doi":"10.4230/LIPIcs.SoCG.2018.46","ddc":["516","000"],"month":"06","language":[{"iso":"eng"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"alternative_title":["LIPIcs"],"file":[{"file_name":"2018_LIPIcs_Huszar.pdf","content_type":"application/pdf","relation":"main_file","creator":"dernst","file_id":"5713","file_size":642522,"access_level":"open_access","checksum":"530d084116778135d5bffaa317479cac","date_created":"2018-12-17T15:32:38Z","date_updated":"2020-07-14T12:45:51Z"}],"volume":99,"oa_version":"Submitted Version","quality_controlled":"1","publication_identifier":{"issn":["18688969"]},"day":"01","article_number":"46","citation":{"short":"K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">10.4230/LIPIcs.SoCG.2018.46</a>","mla":"Huszár, Kristóf, et al. <i>On the Treewidth of Triangulated 3-Manifolds</i>. Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">10.4230/LIPIcs.SoCG.2018.46</a>.","apa":"Huszár, K., Spreer, J., &#38; Wagner, U. (2018). On the treewidth of triangulated 3-manifolds (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>","ista":"Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46."},"oa":1,"status":"public","has_accepted_license":"1","title":"On the treewidth of triangulated 3-manifolds","department":[{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:45:51Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publist_id":"7614","acknowledgement":"Research of the second author was supported by the Einstein Foundation (project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons Visiting Professors” program).","external_id":{"arxiv":["1712.00434"]},"article_processing_charge":"No"},{"status":"public","department":[{"_id":"UlWa"}],"title":"Recognizing weak embeddings of graphs","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"ACM","external_id":{"isi":["000483921200021"],"arxiv":["1709.09209"]},"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.","publist_id":"7556","project":[{"grant_number":"M02281","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs"}],"article_processing_charge":"No","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.09209"}],"page":"274 - 292","oa_version":"Preprint","isi":1,"quality_controlled":"1","day":"01","oa":1,"citation":{"chicago":"Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs,” 274–92. ACM, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.20\">https://doi.org/10.1137/1.9781611975031.20</a>.","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.","short":"H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 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. <i>Recognizing Weak Embeddings of Graphs</i>. ACM, 2018, pp. 274–92, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.20\">10.1137/1.9781611975031.20</a>.","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. In: ACM; 2018:274-292. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.20\">10.1137/1.9781611975031.20</a>","apa":"Akitaya, H., Fulek, R., &#38; 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. <a href=\"https://doi.org/10.1137/1.9781611975031.20\">https://doi.org/10.1137/1.9781611975031.20</a>"},"publication_status":"published","arxiv":1,"type":"conference","date_updated":"2023-09-15T12:19:32Z","doi":"10.1137/1.9781611975031.20","year":"2018","month":"01","language":[{"iso":"eng"}],"date_published":"2018-01-01T00:00:00Z","scopus_import":"1","date_created":"2018-12-11T11:45:45Z","_id":"309","conference":{"end_date":"2018-01-10","name":"SODA: Symposium on Discrete Algorithms","location":"New Orleans, LA, USA","start_date":"2018-01-07"},"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 &quot; &gt; 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 &quot;untangles&quot; 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."}],"author":[{"first_name":"Hugo","last_name":"Akitaya","full_name":"Akitaya, Hugo"},{"last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Tóth, Csaba","last_name":"Tóth","first_name":"Csaba"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"6982"}]}},{"date_created":"2018-12-11T11:45:04Z","conference":{"start_date":"2018-06-11","location":"Budapest, Hungary","name":"SoCG: Symposium on Computational Geometry","end_date":"2018-06-14"},"_id":"184","scopus_import":1,"date_published":"2018-06-11T00:00:00Z","related_material":{"record":[{"id":"7108","relation":"later_version","status":"public"}]},"abstract":[{"text":"We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.","lang":"eng"}],"author":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Patakova","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin","first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer"},{"first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2023-09-06T11:10:57Z","type":"conference","intvolume":"        99","publication_status":"published","month":"06","language":[{"iso":"eng"}],"year":"2018","doi":"10.4230/LIPIcs.SoCG.2018.41","ddc":["516","000"],"file":[{"file_size":718414,"content_type":"application/pdf","relation":"main_file","file_name":"2018_LIPIcs_Goaoc.pdf","creator":"dernst","file_id":"5725","date_created":"2018-12-17T16:35:02Z","date_updated":"2020-07-14T12:45:18Z","checksum":"d12bdd60f04a57307867704b5f930afd","access_level":"open_access"}],"oa_version":"Published Version","page":"41:1 - 41:16","volume":99,"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"day":"11","citation":{"short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16.","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, p. 41:1-41:16.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete,” 99:41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2018). Shellability is NP-complete (Vol. 99, p. 41:1-41:16). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">10.4230/LIPIcs.SoCG.2018.41</a>","mla":"Goaoc, Xavier, et al. <i>Shellability Is NP-Complete</i>. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">10.4230/LIPIcs.SoCG.2018.41</a>.","ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2018. Shellability is NP-complete. SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in Information, LIPIcs, vol. 99, 41:1-41:16."},"oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","has_accepted_license":"1","status":"public","department":[{"_id":"UlWa"}],"title":"Shellability is NP-complete","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:45:18Z","publist_id":"7736","acknowledgement":"Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration."},{"quality_controlled":"1","publication_identifier":{"isbn":["978-3-95977-066-8"]},"article_number":"39","day":"01","oa":1,"citation":{"ieee":"R. Fulek and J. Kynčl, “Hanani-Tutte for approximating maps of graphs,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","chicago":"Fulek, Radoslav, and Jan Kynčl. “Hanani-Tutte for Approximating Maps of Graphs,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">https://doi.org/10.4230/LIPIcs.SoCG.2018.39</a>.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","ista":"Fulek R, Kynčl J. 2018. Hanani-Tutte for approximating maps of graphs. SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in Information, LIPIcs, vol. 99, 39.","mla":"Fulek, Radoslav, and Jan Kynčl. <i>Hanani-Tutte for Approximating Maps of Graphs</i>. Vol. 99, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">10.4230/LIPIcs.SoCG.2018.39</a>.","ama":"Fulek R, Kynčl J. Hanani-Tutte for approximating maps of graphs. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">10.4230/LIPIcs.SoCG.2018.39</a>","apa":"Fulek, R., &#38; Kynčl, J. (2018). Hanani-Tutte for approximating maps of graphs (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">https://doi.org/10.4230/LIPIcs.SoCG.2018.39</a>"},"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"file":[{"file_id":"5701","creator":"dernst","relation":"main_file","content_type":"application/pdf","file_name":"2018_LIPIcs_Fulek.pdf","file_size":718857,"access_level":"open_access","checksum":"f1b94f1a75b37c414a1f61d59fb2cd4c","date_updated":"2020-07-14T12:45:19Z","date_created":"2018-12-17T12:33:52Z"}],"oa_version":"Published Version","volume":99,"publist_id":"7735","project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"title":"Hanani-Tutte for approximating maps of graphs","department":[{"_id":"UlWa"}],"status":"public","has_accepted_license":"1","file_date_updated":"2020-07-14T12:45:19Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jan","last_name":"Kynčl","full_name":"Kynčl, Jan"}],"abstract":[{"lang":"eng","text":"We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint &quot;pipes&quot; corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once."}],"date_published":"2018-01-01T00:00:00Z","scopus_import":1,"date_created":"2018-12-11T11:45:04Z","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2018-06-14","start_date":"2018-06-11","location":"Budapest, Hungary"},"_id":"185","doi":"10.4230/LIPIcs.SoCG.2018.39","year":"2018","ddc":["510"],"month":"01","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"        99","type":"conference","date_updated":"2021-01-12T06:53:36Z"},{"month":"06","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2018.40","year":"2018","type":"conference","arxiv":1,"date_updated":"2023-08-14T12:43:51Z","publication_status":"published","intvolume":"        99","related_material":{"record":[{"id":"11593","status":"public","relation":"later_version"}]},"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav"},{"first_name":"Jan","last_name":"Kynčl","full_name":"Kynčl, Jan"}],"abstract":[{"lang":"eng","text":"A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t × t grid or one of the following so-called t-Kuratowski graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the ℤ2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its ℤ2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces."}],"date_created":"2018-12-11T11:45:05Z","_id":"186","conference":{"end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry","location":"Budapest, Hungary","start_date":"2018-06-11"},"date_published":"2018-06-11T00:00:00Z","scopus_import":"1","article_processing_charge":"No","external_id":{"arxiv":["1803.05085"]},"publist_id":"7734","project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","status":"public","department":[{"_id":"UlWa"}],"title":"The ℤ2-Genus of Kuratowski minors","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"11","oa":1,"citation":{"ieee":"R. Fulek and J. Kynčl, “The ℤ2-Genus of Kuratowski minors,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, p. 40.1-40.14.","chicago":"Fulek, Radoslav, and Jan Kynčl. “The ℤ2-Genus of Kuratowski Minors,” 99:40.1-40.14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">https://doi.org/10.4230/LIPIcs.SoCG.2018.40</a>.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14.","ista":"Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 40.1-40.14.","ama":"Fulek R, Kynčl J. The ℤ2-Genus of Kuratowski minors. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:40.1-40.14. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">10.4230/LIPIcs.SoCG.2018.40</a>","mla":"Fulek, Radoslav, and Jan Kynčl. <i>The ℤ2-Genus of Kuratowski Minors</i>. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">10.4230/LIPIcs.SoCG.2018.40</a>.","apa":"Fulek, R., &#38; Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol. 99, p. 40.1-40.14). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">https://doi.org/10.4230/LIPIcs.SoCG.2018.40</a>"},"quality_controlled":"1","page":"40.1 - 40.14","oa_version":"Submitted Version","volume":99,"main_file_link":[{"url":"https://arxiv.org/abs/1803.05085","open_access":"1"}],"alternative_title":["LIPIcs"]},{"publisher":"Springer","file_date_updated":"2020-07-14T12:47:40Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","department":[{"_id":"UlWa"}],"title":"Computing simplicial representatives of homotopy group elements","status":"public","publication":"Journal of Applied and Computational Topology","project":[{"_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"M01980","name":"Robust invariants of Nonlinear Systems"},{"name":"FWF Open Access Fund","call_identifier":"FWF","_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1"}],"page":"177-231","oa_version":"Published Version","volume":2,"article_type":"original","file":[{"checksum":"cf9e7fcd2a113dd4828774fc75cdb7e8","access_level":"open_access","date_updated":"2020-07-14T12:47:40Z","date_created":"2019-08-08T06:55:21Z","file_id":"6775","creator":"dernst","relation":"main_file","content_type":"application/pdf","file_name":"2018_JourAppliedComputTopology_Filakovsky.pdf","file_size":1056278}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"oa":1,"citation":{"apa":"Filakovský, M., Franek, P., Wagner, U., &#38; Zhechev, S. Y. (2018). Computing simplicial representatives of homotopy group elements. <i>Journal of Applied and Computational Topology</i>. Springer. <a href=\"https://doi.org/10.1007/s41468-018-0021-5\">https://doi.org/10.1007/s41468-018-0021-5</a>","mla":"Filakovský, Marek, et al. “Computing Simplicial Representatives of Homotopy Group Elements.” <i>Journal of Applied and Computational Topology</i>, vol. 2, no. 3–4, Springer, 2018, pp. 177–231, doi:<a href=\"https://doi.org/10.1007/s41468-018-0021-5\">10.1007/s41468-018-0021-5</a>.","ama":"Filakovský M, Franek P, Wagner U, Zhechev SY. Computing simplicial representatives of homotopy group elements. <i>Journal of Applied and Computational Topology</i>. 2018;2(3-4):177-231. doi:<a href=\"https://doi.org/10.1007/s41468-018-0021-5\">10.1007/s41468-018-0021-5</a>","ista":"Filakovský M, Franek P, Wagner U, Zhechev SY. 2018. Computing simplicial representatives of homotopy group elements. Journal of Applied and Computational Topology. 2(3–4), 177–231.","short":"M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and Computational Topology 2 (2018) 177–231.","ieee":"M. Filakovský, P. Franek, U. Wagner, and S. Y. Zhechev, “Computing simplicial representatives of homotopy group elements,” <i>Journal of Applied and Computational Topology</i>, vol. 2, no. 3–4. Springer, pp. 177–231, 2018.","chicago":"Filakovský, Marek, Peter Franek, Uli Wagner, and Stephan Y Zhechev. “Computing Simplicial Representatives of Homotopy Group Elements.” <i>Journal of Applied and Computational Topology</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s41468-018-0021-5\">https://doi.org/10.1007/s41468-018-0021-5</a>."},"day":"01","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"quality_controlled":"1","type":"journal_article","date_updated":"2023-09-07T13:10:36Z","publication_status":"published","intvolume":"         2","language":[{"iso":"eng"}],"month":"12","ddc":["514"],"doi":"10.1007/s41468-018-0021-5","year":"2018","_id":"6774","date_created":"2019-08-08T06:47:40Z","date_published":"2018-12-01T00:00:00Z","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"6681"}]},"issue":"3-4","abstract":[{"text":"A central problem of algebraic topology is to understand the homotopy groups  𝜋𝑑(𝑋)  of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group  𝜋1(𝑋)  of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with   𝜋1(𝑋)  trivial), compute the higher homotopy group   𝜋𝑑(𝑋)  for any given   𝑑≥2 . However, these algorithms come with a caveat: They compute the isomorphism type of   𝜋𝑑(𝑋) ,   𝑑≥2  as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of   𝜋𝑑(𝑋) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere   𝑆𝑑  to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes   𝜋𝑑(𝑋)  and represents its elements as simplicial maps from a suitable triangulation of the d-sphere   𝑆𝑑  to X. For fixed d, the algorithm runs in time exponential in   size(𝑋) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed   𝑑≥2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of   𝜋𝑑(𝑋) , the size of the triangulation of   𝑆𝑑  on which the map is defined, is exponential in size(𝑋) .","lang":"eng"}],"author":[{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","last_name":"Filakovský","first_name":"Marek","full_name":"Filakovský, Marek"},{"id":"473294AE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8878-8397","last_name":"Franek","first_name":"Peter","full_name":"Franek, Peter"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"id":"3AA52972-F248-11E8-B48F-1D18A9856A87","last_name":"Zhechev","first_name":"Stephan Y","full_name":"Zhechev, Stephan Y"}]},{"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file_date_updated":"2020-07-14T12:47:58Z","title":"On expansion and topological overlap","department":[{"_id":"UlWa"}],"status":"public","has_accepted_license":"1","publisher":"Springer","project":[{"grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"publist_id":"6925","external_id":{"isi":["000437122700017"]},"article_processing_charge":"Yes (via OA deal)","publication":"Geometriae Dedicata","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"oa_version":"Published Version","volume":195,"page":"307–317","file":[{"relation":"main_file","content_type":"application/pdf","file_name":"s10711-017-0291-4.pdf","creator":"kschuh","file_id":"5835","file_size":412486,"checksum":"d2f70fc132156504aa4c626aa378a7ab","access_level":"open_access","date_created":"2019-01-15T13:44:05Z","date_updated":"2020-07-14T12:47:58Z"}],"quality_controlled":"1","isi":1,"citation":{"short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>.","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” <i>Geometriae Dedicata</i>, vol. 195, no. 1. Springer, pp. 307–317, 2018.","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. <i>Geometriae Dedicata</i>. 2018;195(1):307–317. doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>","mla":"Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>.","apa":"Dotterrer, D., Kaufman, T., &#38; Wagner, U. (2018). On expansion and topological overlap. <i>Geometriae Dedicata</i>. Springer. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>","ista":"Dotterrer D, Kaufman T, Wagner U. 2018. On expansion and topological overlap. Geometriae Dedicata. 195(1), 307–317."},"oa":1,"day":"01","intvolume":"       195","publication_status":"published","date_updated":"2023-09-27T12:29:57Z","type":"journal_article","ddc":["514","516"],"year":"2018","doi":"10.1007/s10711-017-0291-4","language":[{"iso":"eng"}],"month":"08","scopus_import":"1","date_published":"2018-08-01T00:00:00Z","_id":"742","date_created":"2018-12-11T11:48:16Z","issue":"1","abstract":[{"lang":"eng","text":"We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M."}],"author":[{"full_name":"Dotterrer, Dominic","last_name":"Dotterrer","first_name":"Dominic"},{"full_name":"Kaufman, Tali","last_name":"Kaufman","first_name":"Tali"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1378"}]},"pubrep_id":"912"},{"status":"public","department":[{"_id":"UlWa"}],"title":"Crossing minimization in perturbed drawings","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer","external_id":{"isi":["000672802500016"],"arxiv":["1808.07608"]},"article_processing_charge":"No","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1808.07608"}],"alternative_title":["LNCS"],"oa_version":"Preprint","page":"229-241","volume":"11282 ","isi":1,"quality_controlled":"1","publication_identifier":{"isbn":["9783030044138"]},"day":"18","oa":1,"citation":{"short":"R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.","chicago":"Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed Drawings,” 11282:229–41. Springer, 2018. <a href=\"https://doi.org/10.1007/978-3-030-04414-5_16\">https://doi.org/10.1007/978-3-030-04414-5_16</a>.","ieee":"R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented at the Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol. 11282, pp. 229–241.","apa":"Fulek, R., &#38; Tóth, C. D. (2018). Crossing minimization in perturbed drawings (Vol. 11282, pp. 229–241). Presented at the Graph Drawing and Network Visualization, Barcelona, Spain: Springer. <a href=\"https://doi.org/10.1007/978-3-030-04414-5_16\">https://doi.org/10.1007/978-3-030-04414-5_16</a>","ama":"Fulek R, Tóth CD. Crossing minimization in perturbed drawings. In: Vol 11282. Springer; 2018:229-241. doi:<a href=\"https://doi.org/10.1007/978-3-030-04414-5_16\">10.1007/978-3-030-04414-5_16</a>","mla":"Fulek, Radoslav, and Csaba D. Tóth. <i>Crossing Minimization in Perturbed Drawings</i>. Vol. 11282, Springer, 2018, pp. 229–41, doi:<a href=\"https://doi.org/10.1007/978-3-030-04414-5_16\">10.1007/978-3-030-04414-5_16</a>.","ista":"Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241."},"publication_status":"published","type":"conference","arxiv":1,"date_updated":"2023-09-11T12:49:55Z","doi":"10.1007/978-3-030-04414-5_16","year":"2018","month":"12","language":[{"iso":"eng"}],"date_published":"2018-12-18T00:00:00Z","scopus_import":"1","date_created":"2018-12-30T22:59:15Z","_id":"5791","conference":{"end_date":"2018-09-28","name":"Graph Drawing and Network Visualization","start_date":"2018-09-26","location":"Barcelona, Spain"},"abstract":[{"text":"Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily small ε>0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An ε-perturbation, for every ε>0, is given by a piecewise linear map (Formula Presented), where with ||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths.","lang":"eng"}],"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav"},{"first_name":"Csaba D.","last_name":"Tóth","full_name":"Tóth, Csaba D."}]},{"main_file_link":[{"url":"https://arxiv.org/abs/1712.01341","open_access":"1"}],"oa_version":"Preprint","volume":37,"page":"1500-1516","isi":1,"quality_controlled":"1","publication_identifier":{"eissn":["1741-3176"],"issn":["0278-3649"]},"day":"24","oa":1,"citation":{"ista":"Rohou S, Franek P, Aubry C, Jaulin L. 2018. Proving the existence of loops in robot trajectories. The International Journal of Robotics Research. 37(12), 1500–1516.","apa":"Rohou, S., Franek, P., Aubry, C., &#38; Jaulin, L. (2018). Proving the existence of loops in robot trajectories. <i>The International Journal of Robotics Research</i>. SAGE Publications. <a href=\"https://doi.org/10.1177/0278364918808367\">https://doi.org/10.1177/0278364918808367</a>","ama":"Rohou S, Franek P, Aubry C, Jaulin L. Proving the existence of loops in robot trajectories. <i>The International Journal of Robotics Research</i>. 2018;37(12):1500-1516. doi:<a href=\"https://doi.org/10.1177/0278364918808367\">10.1177/0278364918808367</a>","mla":"Rohou, Simon, et al. “Proving the Existence of Loops in Robot Trajectories.” <i>The International Journal of Robotics Research</i>, vol. 37, no. 12, SAGE Publications, 2018, pp. 1500–16, doi:<a href=\"https://doi.org/10.1177/0278364918808367\">10.1177/0278364918808367</a>.","ieee":"S. Rohou, P. Franek, C. Aubry, and L. Jaulin, “Proving the existence of loops in robot trajectories,” <i>The International Journal of Robotics Research</i>, vol. 37, no. 12. SAGE Publications, pp. 1500–1516, 2018.","chicago":"Rohou, Simon, Peter Franek, Clément Aubry, and Luc Jaulin. “Proving the Existence of Loops in Robot Trajectories.” <i>The International Journal of Robotics Research</i>. SAGE Publications, 2018. <a href=\"https://doi.org/10.1177/0278364918808367\">https://doi.org/10.1177/0278364918808367</a>.","short":"S. Rohou, P. Franek, C. Aubry, L. Jaulin, The International Journal of Robotics Research 37 (2018) 1500–1516."},"department":[{"_id":"UlWa"}],"status":"public","title":"Proving the existence of loops in robot trajectories","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"SAGE Publications","external_id":{"arxiv":["1712.01341"],"isi":["000456881100004"]},"publication":"The International Journal of Robotics Research","article_processing_charge":"No","date_published":"2018-10-24T00:00:00Z","scopus_import":"1","date_created":"2019-02-13T09:36:20Z","_id":"5960","author":[{"first_name":"Simon","last_name":"Rohou","full_name":"Rohou, Simon"},{"full_name":"Franek, Peter","first_name":"Peter","orcid":"0000-0001-8878-8397","last_name":"Franek","id":"473294AE-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Clément","last_name":"Aubry","full_name":"Aubry, Clément"},{"full_name":"Jaulin, Luc","first_name":"Luc","last_name":"Jaulin"}],"abstract":[{"text":"In this paper we present a reliable method to verify the existence of loops along the uncertain trajectory of a robot, based on proprioceptive measurements only, within a bounded-error context. The loop closure detection is one of the key points in simultaneous localization and mapping (SLAM) methods, especially in homogeneous environments with difficult scenes recognitions. The proposed approach is generic and could be coupled with conventional SLAM algorithms to reliably reduce their computing burden, thus improving the localization and mapping processes in the most challenging environments such as unexplored underwater extents. To prove that a robot performed a loop whatever the uncertainties in its evolution, we employ the notion of topological degree that originates in the field of differential topology. We show that a verification tool based on the topological degree is an optimal method for proving robot loops. This is demonstrated both on datasets from real missions involving autonomous underwater vehicles and by a mathematical discussion.","lang":"eng"}],"issue":"12","publication_status":"published","intvolume":"        37","type":"journal_article","arxiv":1,"date_updated":"2023-09-19T10:41:59Z","doi":"10.1177/0278364918808367","year":"2018","month":"10","language":[{"iso":"eng"}]},{"date_published":"2018-05-31T00:00:00Z","date_created":"2019-04-30T06:09:57Z","_id":"6355","ec_funded":1,"author":[{"first_name":"Arseniy","orcid":"0000-0002-2548-617X","last_name":"Akopyan","full_name":"Akopyan, Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87"},{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov","first_name":"Sergey","full_name":"Avvakumov, Sergey"}],"abstract":[{"text":"We  prove  that  any  cyclic  quadrilateral  can  be  inscribed  in  any  closed  convex C1-curve.  The smoothness condition is not required if the quadrilateral is a rectangle.","lang":"eng"}],"related_material":{"record":[{"id":"8156","relation":"dissertation_contains","status":"public"}]},"intvolume":"         6","publication_status":"published","date_updated":"2023-09-19T14:50:12Z","arxiv":1,"type":"journal_article","year":"2018","doi":"10.1017/fms.2018.7","ddc":["510"],"month":"05","language":[{"iso":"eng"}],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"file":[{"file_size":249246,"file_id":"6356","creator":"dernst","file_name":"2018_ForumMahtematics_Akopyan.pdf","content_type":"application/pdf","relation":"main_file","date_updated":"2020-07-14T12:47:28Z","date_created":"2019-04-30T06:14:58Z","access_level":"open_access","checksum":"5a71b24ba712a3eb2e46165a38fbc30a"}],"volume":6,"oa_version":"Published Version","quality_controlled":"1","isi":1,"publication_identifier":{"issn":["2050-5094"]},"day":"31","article_number":"e7","citation":{"ieee":"A. Akopyan and S. Avvakumov, “Any cyclic quadrilateral can be inscribed in any closed convex smooth curve,” <i>Forum of Mathematics, Sigma</i>, vol. 6. Cambridge University Press, 2018.","chicago":"Akopyan, Arseniy, and Sergey Avvakumov. “Any Cyclic Quadrilateral Can Be Inscribed in Any Closed Convex Smooth Curve.” <i>Forum of Mathematics, Sigma</i>. Cambridge University Press, 2018. <a href=\"https://doi.org/10.1017/fms.2018.7\">https://doi.org/10.1017/fms.2018.7</a>.","short":"A. Akopyan, S. Avvakumov, Forum of Mathematics, Sigma 6 (2018).","ista":"Akopyan A, Avvakumov S. 2018. Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. Forum of Mathematics, Sigma. 6, e7.","apa":"Akopyan, A., &#38; Avvakumov, S. (2018). Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. <i>Forum of Mathematics, Sigma</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2018.7\">https://doi.org/10.1017/fms.2018.7</a>","ama":"Akopyan A, Avvakumov S. Any cyclic quadrilateral can be inscribed in any closed convex smooth curve. <i>Forum of Mathematics, Sigma</i>. 2018;6. doi:<a href=\"https://doi.org/10.1017/fms.2018.7\">10.1017/fms.2018.7</a>","mla":"Akopyan, Arseniy, and Sergey Avvakumov. “Any Cyclic Quadrilateral Can Be Inscribed in Any Closed Convex Smooth Curve.” <i>Forum of Mathematics, Sigma</i>, vol. 6, e7, Cambridge University Press, 2018, doi:<a href=\"https://doi.org/10.1017/fms.2018.7\">10.1017/fms.2018.7</a>."},"oa":1,"has_accepted_license":"1","status":"public","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"JaMa"}],"title":"Any cyclic quadrilateral can be inscribed in any closed convex smooth curve","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file_date_updated":"2020-07-14T12:47:28Z","publisher":"Cambridge University Press","external_id":{"arxiv":["1712.10205"],"isi":["000433915500001"]},"project":[{"name":"Optimal Transport and Stochastic Dynamics","_id":"256E75B8-B435-11E9-9278-68D0E5697425","grant_number":"716117","call_identifier":"H2020"}],"publication":"Forum of Mathematics, Sigma","article_processing_charge":"No"},{"main_file_link":[{"url":"https://arxiv.org/abs/1402.0815","open_access":"1"}],"oa_version":"Preprint","volume":65,"article_type":"original","isi":1,"quality_controlled":"1","oa":1,"citation":{"apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2018). Embeddability in the 3-Sphere is decidable. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3078632\">https://doi.org/10.1145/3078632</a>","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3-Sphere is decidable. <i>Journal of the ACM</i>. 2018;65(1). doi:<a href=\"https://doi.org/10.1145/3078632\">10.1145/3078632</a>","mla":"Matoušek, Jiří, et al. “Embeddability in the 3-Sphere Is Decidable.” <i>Journal of the ACM</i>, vol. 65, no. 1, 5, ACM, 2018, doi:<a href=\"https://doi.org/10.1145/3078632\">10.1145/3078632</a>.","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2018. Embeddability in the 3-Sphere is decidable. Journal of the ACM. 65(1), 5.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018).","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3-Sphere Is Decidable.” <i>Journal of the ACM</i>. ACM, 2018. <a href=\"https://doi.org/10.1145/3078632\">https://doi.org/10.1145/3078632</a>.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3-Sphere is decidable,” <i>Journal of the ACM</i>, vol. 65, no. 1. ACM, 2018."},"article_number":"5","day":"01","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Embeddability in the 3-Sphere is decidable","department":[{"_id":"UlWa"}],"status":"public","publisher":"ACM","project":[{"grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme"}],"external_id":{"arxiv":["1402.0815"],"isi":["000425685900006"]},"publist_id":"7398","article_processing_charge":"No","publication":"Journal of the ACM","date_published":"2018-01-01T00:00:00Z","scopus_import":"1","_id":"425","date_created":"2018-12-11T11:46:24Z","issue":"1","abstract":[{"lang":"eng","text":"We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, that is, an essential curve in the boundary of X bounding a disk in S3 \\ X with length bounded by a computable function of the number of tetrahedra of X."}],"ec_funded":1,"author":[{"first_name":"Jiří","last_name":"Matoušek","full_name":"Matoušek, Jiří"},{"full_name":"Sedgwick, Eric","last_name":"Sedgwick","first_name":"Eric"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2157"}]},"publication_status":"published","intvolume":"        65","type":"journal_article","arxiv":1,"date_updated":"2023-09-11T13:38:49Z","doi":"10.1145/3078632","year":"2018","language":[{"iso":"eng"}],"month":"01"},{"abstract":[{"lang":"eng","text":"A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is 3/2(n-1), and that this bound is best possible for infinitely many values of n."}],"author":[{"first_name":"Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pach","first_name":"János","full_name":"Pach, János"}],"related_material":{"record":[{"id":"5857","status":"public","relation":"later_version"}]},"date_published":"2018-01-21T00:00:00Z","scopus_import":1,"date_created":"2018-12-11T11:46:27Z","_id":"433","conference":{"location":"Boston, MA, United States","start_date":"201-09-25","end_date":"2017-09-27","name":"GD 2017: Graph Drawing and Network Visualization"},"doi":"10.1007/978-3-319-73915-1_14","year":"2018","month":"01","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"     10692","type":"conference","arxiv":1,"date_updated":"2023-08-24T14:39:32Z","quality_controlled":"1","day":"21","oa":1,"citation":{"ama":"Fulek R, Pach J. Thrackles: An improved upper bound. In: Vol 10692. Springer; 2018:160-166. doi:<a href=\"https://doi.org/10.1007/978-3-319-73915-1_14\">10.1007/978-3-319-73915-1_14</a>","mla":"Fulek, Radoslav, and János Pach. <i>Thrackles: An Improved Upper Bound</i>. Vol. 10692, Springer, 2018, pp. 160–66, doi:<a href=\"https://doi.org/10.1007/978-3-319-73915-1_14\">10.1007/978-3-319-73915-1_14</a>.","apa":"Fulek, R., &#38; Pach, J. (2018). Thrackles: An improved upper bound (Vol. 10692, pp. 160–166). Presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-319-73915-1_14\">https://doi.org/10.1007/978-3-319-73915-1_14</a>","ista":"Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD 2017: Graph Drawing and Network Visualization, LNCS, vol. 10692, 160–166.","short":"R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound,” 10692:160–66. Springer, 2018. <a href=\"https://doi.org/10.1007/978-3-319-73915-1_14\">https://doi.org/10.1007/978-3-319-73915-1_14</a>.","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States, 2018, vol. 10692, pp. 160–166."},"main_file_link":[{"url":"https://arxiv.org/abs/1708.08037","open_access":"1"}],"alternative_title":["LNCS"],"volume":10692,"page":"160 - 166","oa_version":"Submitted Version","external_id":{"arxiv":["1708.08037"]},"publist_id":"7390","department":[{"_id":"UlWa"}],"title":"Thrackles: An improved upper bound","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer"},{"publisher":"Springer","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","department":[{"_id":"UlWa"}],"title":"Algorithmic solvability of the lifting extension problem","status":"public","article_processing_charge":"No","publication":"Discrete & Computational Geometry","external_id":{"isi":["000400072700008"]},"publist_id":"6309","page":"915 - 965","oa_version":"Submitted Version","volume":54,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1307.6444"}],"oa":1,"citation":{"short":"M. Čadek, M. Krcál, L. Vokřínek, Discrete &#38; Computational Geometry 54 (2017) 915–965.","ieee":"M. Čadek, M. Krcál, and L. Vokřínek, “Algorithmic solvability of the lifting extension problem,” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 4. Springer, pp. 915–965, 2017.","chicago":"Čadek, Martin, Marek Krcál, and Lukáš Vokřínek. “Algorithmic Solvability of the Lifting Extension Problem.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00454-016-9855-6\">https://doi.org/10.1007/s00454-016-9855-6</a>.","mla":"Čadek, Martin, et al. “Algorithmic Solvability of the Lifting Extension Problem.” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 4, Springer, 2017, pp. 915–65, doi:<a href=\"https://doi.org/10.1007/s00454-016-9855-6\">10.1007/s00454-016-9855-6</a>.","ama":"Čadek M, Krcál M, Vokřínek L. Algorithmic solvability of the lifting extension problem. <i>Discrete &#38; Computational Geometry</i>. 2017;54(4):915-965. doi:<a href=\"https://doi.org/10.1007/s00454-016-9855-6\">10.1007/s00454-016-9855-6</a>","apa":"Čadek, M., Krcál, M., &#38; Vokřínek, L. (2017). Algorithmic solvability of the lifting extension problem. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-016-9855-6\">https://doi.org/10.1007/s00454-016-9855-6</a>","ista":"Čadek M, Krcál M, Vokřínek L. 2017. Algorithmic solvability of the lifting extension problem. Discrete &#38; Computational Geometry. 54(4), 915–965."},"day":"01","publication_identifier":{"issn":["01795376"]},"isi":1,"quality_controlled":"1","type":"journal_article","date_updated":"2023-09-20T12:01:28Z","publication_status":"published","intvolume":"        54","language":[{"iso":"eng"}],"month":"06","doi":"10.1007/s00454-016-9855-6","year":"2017","_id":"1073","date_created":"2018-12-11T11:50:00Z","date_published":"2017-06-01T00:00:00Z","scopus_import":"1","issue":"4","abstract":[{"lang":"eng","text":"Let X and Y be finite simplicial sets (e.g. finite simplicial complexes), both equipped with a free simplicial action of a finite group G. Assuming that Y is d-connected and dimX≤2d, for some d≥1, we provide an algorithm that computes the set of all equivariant homotopy classes of equivariant continuous maps |X|→|Y|; the existence of such a map can be decided even for dimX≤2d+1. This yields the first algorithm for deciding topological embeddability of a k-dimensional finite simplicial complex into Rn under the condition k≤23n−1. More generally, we present an algorithm that, given a lifting-extension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the non-equivariant situation."}],"author":[{"last_name":"Čadek","first_name":"Martin","full_name":"Čadek, Martin"},{"last_name":"Krcál","first_name":"Marek","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Lukáš","last_name":"Vokřínek","full_name":"Vokřínek, Lukáš"}]}]