[{"_id":"1408","file_date_updated":"2020-07-14T12:44:53Z","doi":"10.1007/s00454-016-9794-2","citation":{"chicago":"Franek, Peter, and Marek Krcál. “On Computability and Triviality of Well Groups.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s00454-016-9794-2\">https://doi.org/10.1007/s00454-016-9794-2</a>.","mla":"Franek, Peter, and Marek Krcál. “On Computability and Triviality of Well Groups.” <i>Discrete &#38; Computational Geometry</i>, vol. 56, no. 1, Springer, 2016, pp. 126–64, doi:<a href=\"https://doi.org/10.1007/s00454-016-9794-2\">10.1007/s00454-016-9794-2</a>.","ista":"Franek P, Krcál M. 2016. On computability and triviality of well groups. Discrete &#38; Computational Geometry. 56(1), 126–164.","ieee":"P. Franek and M. Krcál, “On computability and triviality of well groups,” <i>Discrete &#38; Computational Geometry</i>, vol. 56, no. 1. Springer, pp. 126–164, 2016.","ama":"Franek P, Krcál M. On computability and triviality of well groups. <i>Discrete &#38; Computational Geometry</i>. 2016;56(1):126-164. doi:<a href=\"https://doi.org/10.1007/s00454-016-9794-2\">10.1007/s00454-016-9794-2</a>","short":"P. Franek, M. Krcál, Discrete &#38; Computational Geometry 56 (2016) 126–164.","apa":"Franek, P., &#38; Krcál, M. (2016). On computability and triviality of well groups. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-016-9794-2\">https://doi.org/10.1007/s00454-016-9794-2</a>"},"date_created":"2018-12-11T11:51:51Z","publist_id":"5799","year":"2016","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). ","related_material":{"record":[{"status":"public","id":"1510","relation":"earlier_version"}]},"ec_funded":1,"project":[{"grant_number":"M01980","_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","name":"Robust invariants of Nonlinear Systems","call_identifier":"FWF"},{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"quality_controlled":"1","volume":56,"page":"126 - 164","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"date_published":"2016-07-01T00:00:00Z","license":"https://creativecommons.org/licenses/by/4.0/","publisher":"Springer","publication_status":"published","abstract":[{"lang":"eng","text":"The concept of well group in a special but important case captures homological properties of the zero set of a continuous map (Formula presented.) on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within (Formula presented.) distance r from f for a given (Formula presented.). The main drawback of the approach is that the computability of well groups was shown only when (Formula presented.) or (Formula presented.). Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of (Formula presented.) by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and (Formula presented.), our approximation of the (Formula presented.)th well group is exact. For the second part, we find examples of maps (Formula presented.) with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["510"],"language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","title":"On computability and triviality of well groups","article_processing_charge":"Yes (via OA deal)","issue":"1","date_updated":"2023-02-23T10:02:11Z","oa":1,"pubrep_id":"614","has_accepted_license":"1","scopus_import":1,"intvolume":"        56","status":"public","type":"journal_article","author":[{"last_name":"Franek","id":"473294AE-F248-11E8-B48F-1D18A9856A87","full_name":"Franek, Peter","first_name":"Peter"},{"first_name":"Marek","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál"}],"file":[{"file_name":"IST-2016-614-v1+1_s00454-016-9794-2.pdf","checksum":"e0da023abf6b72abd8c6a8c76740d53c","file_id":"4846","date_updated":"2020-07-14T12:44:53Z","date_created":"2018-12-12T10:10:55Z","creator":"system","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":905303}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"01","month":"07"},{"scopus_import":1,"intvolume":"       212","title":"Untangling two systems of noncrossing curves","issue":"1","oa":1,"date_updated":"2023-02-23T10:34:31Z","publication":"Israel Journal of Mathematics","language":[{"iso":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"http://arxiv.org/abs/1302.6475","open_access":"1"}],"oa_version":"Preprint","day":"01","month":"05","author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"last_name":"Sedgwick","full_name":"Sedgwick, Eric","first_name":"Eric"},{"full_name":"Tancer, Martin","first_name":"Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer"},{"first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"type":"journal_article","status":"public","related_material":{"record":[{"id":"2244","relation":"earlier_version","status":"public"}]},"citation":{"chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” <i>Israel Journal of Mathematics</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s11856-016-1294-9\">https://doi.org/10.1007/s11856-016-1294-9</a>.","mla":"Matoušek, Jiří, et al. “Untangling Two Systems of Noncrossing Curves.” <i>Israel Journal of Mathematics</i>, vol. 212, no. 1, Springer, 2016, pp. 37–79, doi:<a href=\"https://doi.org/10.1007/s11856-016-1294-9\">10.1007/s11856-016-1294-9</a>.","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2016. Untangling two systems of noncrossing curves. Israel Journal of Mathematics. 212(1), 37–79.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Israel Journal of Mathematics 212 (2016) 37–79.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” <i>Israel Journal of Mathematics</i>, vol. 212, no. 1. Springer, pp. 37–79, 2016.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. <i>Israel Journal of Mathematics</i>. 2016;212(1):37-79. doi:<a href=\"https://doi.org/10.1007/s11856-016-1294-9\">10.1007/s11856-016-1294-9</a>","apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2016). Untangling two systems of noncrossing curves. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-016-1294-9\">https://doi.org/10.1007/s11856-016-1294-9</a>"},"publist_id":"5796","date_created":"2018-12-11T11:51:52Z","year":"2016","acknowledgement":"Supported by the ERC Adv anced Grant No. 267165. ","doi":"10.1007/s11856-016-1294-9","_id":"1411","abstract":[{"text":"We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to “untangle” the βj from the ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov.","lang":"eng"}],"publication_status":"published","volume":212,"quality_controlled":"1","department":[{"_id":"UlWa"}],"page":"37 - 79","date_published":"2016-05-01T00:00:00Z","publisher":"Springer","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}]},{"status":"public","type":"dissertation","alternative_title":["ISTA Thesis"],"file":[{"content_type":"application/pdf","file_size":2227916,"access_level":"closed","relation":"main_file","creator":"dernst","date_updated":"2019-08-13T08:45:27Z","date_created":"2019-08-13T08:45:27Z","file_name":"Thesis_final version_Mabillard_w_signature_page.pdf","checksum":"2d140cc924cd1b764544906fc22684ef","file_id":"6809"},{"access_level":"open_access","relation":"main_file","file_size":2227916,"content_type":"application/pdf","creator":"dernst","date_updated":"2021-02-22T11:36:34Z","date_created":"2021-02-22T11:36:34Z","file_id":"9178","checksum":"2d140cc924cd1b764544906fc22684ef","file_name":"2016_Mabillard_Thesis.pdf","success":1}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","day":"01","oa_version":"Published Version","publication_identifier":{"issn":["2663-337X"]},"month":"08","author":[{"first_name":"Isaac","full_name":"Mabillard, Isaac","last_name":"Mabillard","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","title":"Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture","article_processing_charge":"No","oa":1,"date_updated":"2023-09-07T11:56:28Z","page":"55","department":[{"_id":"UlWa"}],"date_published":"2016-08-01T00:00:00Z","supervisor":[{"orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli"}],"publisher":"Institute of Science and Technology Austria","abstract":[{"text":"Motivated by topological Tverberg-type problems  in topological combinatorics and by classical\r\nresults about embeddings (maps without double points), we study the question whether a finite\r\nsimplicial complex K  can be mapped into Rd  without triple, quadruple, or, more generally, r-fold points  (image points with at least r  distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd  that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint  simplices of K , and we seek necessary and sufficient conditions for the existence of such maps.\r\n\r\nWe present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction  for embeddability of k -dimensional\r\ncomplexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK  = (r ≥ 1)k  and d  = rk \\ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign  can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3.\r\n\r\nAn important guiding idea for our work was that suffciency of the DPC, together with an old\r\nresult of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN  to Rd  without r-Tverberg points when r not a prime power  and\r\nN  = (d  + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K  = σN .\r\n\r\nIn 2015, Frick [16] found a very elegant way to overcome this \\codimension 3 obstacle&quot; and\r\nto construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r  + 1 and r  not a prime power, by a reduction1  to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC.\r\n\r\nIn this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r  not a prime power.     ","lang":"eng"}],"ddc":["500"],"publication_status":"published","_id":"1123","file_date_updated":"2021-02-22T11:36:34Z","related_material":{"record":[{"relation":"part_of_dissertation","id":"2159","status":"public"}]},"degree_awarded":"PhD","publist_id":"6237","date_created":"2018-12-11T11:50:16Z","citation":{"mla":"Mabillard, Isaac. <i>Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture</i>. Institute of Science and Technology Austria, 2016.","ista":"Mabillard I. 2016. Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture. Institute of Science and Technology Austria.","chicago":"Mabillard, Isaac. “Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture.” Institute of Science and Technology Austria, 2016.","short":"I. Mabillard, Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture, Institute of Science and Technology Austria, 2016.","ama":"Mabillard I. Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture. 2016.","ieee":"I. Mabillard, “Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture,” Institute of Science and Technology Austria, 2016.","apa":"Mabillard, I. (2016). <i>Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture</i>. Institute of Science and Technology Austria."},"year":"2016","acknowledgement":"Foremost, I would like to thank Uli Wagner for introducing me to the exciting interface between\r\ntopology and combinatorics, and for our subsequent years of fruitful collaboration.\r\nIn our creative endeavors to eliminate intersection points, we had the chance to be joined later\r\nby Sergey Avvakumov and Arkadiy Skopenkov, which led us to new surprises in dimension 12.\r\nMy stay at EPFL and IST Austria was made very agreeable thanks to all these wonderful\r\npeople: Cyril Becker, Marek Filakovsky, Peter Franek, Radoslav Fulek, Peter Gazi, Kristof Huszar,\r\nMarek Krcal, Zuzana Masarova, Arnaud de Mesmay, Filip Moric, Michal Rybar, Martin Tancer,\r\nand Stephan Zhechev.\r\nFinally, I would like to thank my thesis committee Herbert Edelsbrunner and Roman Karasev\r\nfor their careful reading of the present manuscript and for the many improvements they suggested."},{"date_created":"2018-12-11T11:50:29Z","citation":{"apa":"Fulek, R., Pelsmajer, M., &#38; Schaefer, M. (2016). Hanani-Tutte for radial planarity II (Vol. 9801, pp. 468–481). Presented at the GD: Graph Drawing and Network Visualization, Athens, Greece: Springer. <a href=\"https://doi.org/10.1007/978-3-319-50106-2_36\">https://doi.org/10.1007/978-3-319-50106-2_36</a>","mla":"Fulek, Radoslav, et al. <i>Hanani-Tutte for Radial Planarity II</i>. Vol. 9801, Springer, 2016, pp. 468–81, doi:<a href=\"https://doi.org/10.1007/978-3-319-50106-2_36\">10.1007/978-3-319-50106-2_36</a>.","ista":"Fulek R, Pelsmajer M, Schaefer M. 2016. Hanani-Tutte for radial planarity II. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 468–481.","chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity II,” 9801:468–81. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-50106-2_36\">https://doi.org/10.1007/978-3-319-50106-2_36</a>.","ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity II,” presented at the GD: Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp. 468–481.","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity II. In: Vol 9801. Springer; 2016:468-481. doi:<a href=\"https://doi.org/10.1007/978-3-319-50106-2_36\">10.1007/978-3-319-50106-2_36</a>","short":"R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2016, pp. 468–481."},"publist_id":"6193","year":"2016","related_material":{"record":[{"status":"public","id":"1113","relation":"later_version"},{"status":"public","id":"1595","relation":"earlier_version"}]},"ec_funded":1,"_id":"1164","doi":"10.1007/978-3-319-50106-2_36","publication_status":"published","abstract":[{"lang":"eng","text":"A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, … , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing."}],"external_id":{"arxiv":["1608.08662"]},"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"volume":9801,"quality_controlled":"1","department":[{"_id":"UlWa"}],"page":"468 - 481","date_published":"2016-12-08T00:00:00Z","publisher":"Springer","title":"Hanani-Tutte for radial planarity II","article_processing_charge":"No","oa":1,"date_updated":"2023-02-23T10:05:57Z","intvolume":"      9801","scopus_import":1,"language":[{"iso":"eng"}],"arxiv":1,"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek"},{"last_name":"Pelsmajer","first_name":"Michael","full_name":"Pelsmajer, Michael"},{"first_name":"Marcus","full_name":"Schaefer, Marcus","last_name":"Schaefer"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://arxiv.org/abs/1608.08662","open_access":"1"}],"day":"08","oa_version":"Preprint","month":"12","conference":{"location":"Athens, Greece","end_date":"2016-09-21","name":"GD: Graph Drawing and Network Visualization","start_date":"2016-09-19"},"status":"public","type":"conference","alternative_title":["LNCS"]},{"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","first_name":"Radoslav"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://arxiv.org/abs/1602.01346","open_access":"1"}],"oa_version":"Preprint","day":"08","month":"12","conference":{"location":"Athens, Greece","end_date":"2016-09-21","name":"GD: Graph Drawing and Network Visualization","start_date":"2016-09-19"},"status":"public","type":"conference","alternative_title":["LNCS"],"title":"C-planarity of embedded cyclic c-graphs","oa":1,"date_updated":"2023-09-27T12:14:48Z","scopus_import":1,"language":[{"iso":"eng"}],"publication_status":"published","abstract":[{"text":"We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.","lang":"eng"}],"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734"}],"volume":"9801 ","quality_controlled":"1","department":[{"_id":"UlWa"}],"page":"94 - 106","date_published":"2016-12-08T00:00:00Z","publisher":"Springer","publist_id":"6192","citation":{"short":"R. Fulek, in:, Springer, 2016, pp. 94–106.","ieee":"R. Fulek, “C-planarity of embedded cyclic c-graphs,” presented at the GD: Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp. 94–106.","ama":"Fulek R. C-planarity of embedded cyclic c-graphs. In: Vol 9801. Springer; 2016:94-106. doi:<a href=\"https://doi.org/10.1007/978-3-319-50106-2_8\">10.1007/978-3-319-50106-2_8</a>","mla":"Fulek, Radoslav. <i>C-Planarity of Embedded Cyclic c-Graphs</i>. Vol. 9801, Springer, 2016, pp. 94–106, doi:<a href=\"https://doi.org/10.1007/978-3-319-50106-2_8\">10.1007/978-3-319-50106-2_8</a>.","chicago":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs,” 9801:94–106. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-50106-2_8\">https://doi.org/10.1007/978-3-319-50106-2_8</a>.","ista":"Fulek R. 2016. C-planarity of embedded cyclic c-graphs. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 94–106.","apa":"Fulek, R. (2016). C-planarity of embedded cyclic c-graphs (Vol. 9801, pp. 94–106). Presented at the GD: Graph Drawing and Network Visualization, Athens, Greece: Springer. <a href=\"https://doi.org/10.1007/978-3-319-50106-2_8\">https://doi.org/10.1007/978-3-319-50106-2_8</a>"},"date_created":"2018-12-11T11:50:30Z","year":"2016","acknowledgement":"R. Fulek—The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].\r\nI would like to thank Jan Kynčl and Dömötör Pálvölgyi for many comments and suggestions that helped to improve the presentation of the result.","related_material":{"record":[{"status":"public","relation":"later_version","id":"794"}]},"ec_funded":1,"_id":"1165","doi":"10.1007/978-3-319-50106-2_8"},{"department":[{"_id":"UlWa"}],"status":"public","date_published":"2015-11-15T00:00:00Z","type":"preprint","publication_status":"submitted","author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov","first_name":"Sergey","full_name":"Avvakumov, Sergey"},{"full_name":"Mabillard, Isaac","first_name":"Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard"},{"first_name":"A.","full_name":"Skopenkov, A.","last_name":"Skopenkov"},{"last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli"}],"arxiv":1,"oa_version":"Preprint","day":"15","external_id":{"arxiv":["1511.03501"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1511.03501"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We study conditions under which a finite simplicial complex $K$ can be mapped to $\\mathbb R^d$ without higher-multiplicity intersections. An almost $r$-embedding is a map $f: K\\to \\mathbb R^d$ such that the images of any $r$\r\npairwise disjoint simplices of $K$ do not have a common point. We show that if $r$ is not a prime power and $d\\geq 2r+1$, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost $r$-embedding of\r\nthe $(d+1)(r-1)$-simplex in $\\mathbb R^d$. This improves on previous constructions of counterexamples (for $d\\geq 3r$) based on a series of papers by M. \\\"Ozaydin, M. Gromov, P. Blagojevi\\'c, F. Frick, G. Ziegler, and the second and fourth present authors. The counterexamples are obtained by proving the following algebraic criterion in codimension 2: If $r\\ge3$ and if $K$ is a finite $2(r-1)$-complex then there exists an almost $r$-embedding $K\\to \\mathbb R^{2r}$ if and only if there exists a general position PL map $f:K\\to \\mathbb R^{2r}$ such that the algebraic intersection number of the $f$-images of any $r$ pairwise disjoint simplices of $K$ is zero. This result can be restated in terms of cohomological obstructions or equivariant maps, and extends an analogous codimension 3 criterion by the second and fourth authors. As another application we classify ornaments $f:S^3 \\sqcup S^3\\sqcup S^3\\to \\mathbb R^5$ up to ornament\r\nconcordance. It follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous criterion for $r=2$ is false. We prove a lemma on singular higher-dimensional Borromean rings, yielding an elementary proof of the counterexample."}],"month":"11","_id":"8183","language":[{"iso":"eng"}],"publication":"arXiv","date_created":"2020-07-30T10:45:19Z","title":"Eliminating higher-multiplicity intersections, III. Codimension 2","citation":{"apa":"Avvakumov, S., Mabillard, I., Skopenkov, A., &#38; Wagner, U. (n.d.). Eliminating higher-multiplicity intersections, III. Codimension 2. <i>arXiv</i>.","ama":"Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. <i>arXiv</i>.","ieee":"S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity intersections, III. Codimension 2,” <i>arXiv</i>. .","short":"S. Avvakumov, I. Mabillard, A. Skopenkov, U. Wagner, ArXiv (n.d.).","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>ArXiv</i>, 1511.03501.","chicago":"Avvakumov, Sergey, Isaac Mabillard, A. Skopenkov, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>ArXiv</i>, n.d.","ista":"Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv, 1511.03501."},"date_updated":"2023-09-07T13:12:17Z","oa":1,"acknowledgement":"We would like to thank A. Klyachko, V. Krushkal, S. Melikhov, M. Tancer, P. Teichner and anonymous referees for helpful discussions.","article_processing_charge":"No","year":"2015","related_material":{"record":[{"status":"public","id":"9308","relation":"later_version"},{"status":"public","relation":"later_version","id":"10220"},{"status":"public","relation":"dissertation_contains","id":"8156"}]},"article_number":"1511.03501"},{"doi":"10.4230/LIPIcs.SOCG.2015.842","file_date_updated":"2020-07-14T12:44:59Z","_id":"1510","ec_funded":1,"related_material":{"record":[{"status":"public","relation":"later_version","id":"1408"}]},"citation":{"apa":"Franek, P., &#38; Krcál, M. (2015). On computability and triviality of well groups (Vol. 34, pp. 842–856). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">https://doi.org/10.4230/LIPIcs.SOCG.2015.842</a>","short":"P. Franek, M. Krcál, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 842–856.","ieee":"P. Franek and M. Krcál, “On computability and triviality of well groups,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 842–856.","ama":"Franek P, Krcál M. On computability and triviality of well groups. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:842-856. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">10.4230/LIPIcs.SOCG.2015.842</a>","mla":"Franek, Peter, and Marek Krcál. <i>On Computability and Triviality of Well Groups</i>. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 842–56, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">10.4230/LIPIcs.SOCG.2015.842</a>.","chicago":"Franek, Peter, and Marek Krcál. “On Computability and Triviality of Well Groups,” 34:842–56. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">https://doi.org/10.4230/LIPIcs.SOCG.2015.842</a>.","ista":"Franek P, Krcál M. 2015. On computability and triviality of well groups. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 842–856."},"date_created":"2018-12-11T11:52:26Z","publist_id":"5667","year":"2015","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"page":"842 - 856","quality_controlled":"1","volume":34,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2015-06-11T00:00:00Z","project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"abstract":[{"text":"The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r &gt; 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K &lt; 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status. ","lang":"eng"}],"ddc":["510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published","language":[{"iso":"eng"}],"intvolume":"        34","has_accepted_license":"1","scopus_import":1,"title":"On computability and triviality of well groups","date_updated":"2023-02-21T17:02:57Z","pubrep_id":"503","oa":1,"alternative_title":["LIPIcs"],"status":"public","type":"conference","oa_version":"Published Version","day":"11","file":[{"checksum":"49eb5021caafaabe5356c65b9c5f8c9c","file_id":"5001","file_name":"IST-2016-503-v1+1_32.pdf","date_updated":"2020-07-14T12:44:59Z","date_created":"2018-12-12T10:13:19Z","creator":"system","content_type":"application/pdf","file_size":623563,"relation":"main_file","access_level":"open_access"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2015-06-22","location":"Eindhoven, Netherlands","end_date":"2015-06-25"},"month":"06","author":[{"id":"473294AE-F248-11E8-B48F-1D18A9856A87","last_name":"Franek","first_name":"Peter","full_name":"Franek, Peter"},{"first_name":"Marek","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál"}]},{"doi":"10.4230/LIPIcs.SOCG.2015.476","file_date_updated":"2020-07-14T12:44:59Z","_id":"1511","ec_funded":1,"related_material":{"record":[{"id":"610","relation":"later_version","status":"public"}]},"date_created":"2018-12-11T11:52:27Z","publist_id":"5666","citation":{"ista":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2015. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 476–490.","mla":"Goaoc, Xavier, et al. <i>On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result</i>. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–90, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">10.4230/LIPIcs.SOCG.2015.476</a>.","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result,” 34:476–90. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">https://doi.org/10.4230/LIPIcs.SOCG.2015.476</a>.","ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 476–490.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:476-490. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">10.4230/LIPIcs.SOCG.2015.476</a>","short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–490.","apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2015). On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result (Vol. 34, pp. 476–490). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">https://doi.org/10.4230/LIPIcs.SOCG.2015.476</a>"},"acknowledgement":"The work by Z. P. was partially supported by the Charles University Grant SVV-2014-260103. The\r\nwork by Z. P. and M. T. was partially supported by the project CE-ITI (GACR P202/12/G061) of\r\nthe Czech Science Foundation and by the ERC Advanced Grant No. 267165. Part of the research\r\nwork of M. T. was conducted at IST Austria, supported by an IST Fellowship. The work by U.W.\r\nwas partially supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and\r\nSNSF-PP00P2-138948).","year":"2015","department":[{"_id":"UlWa"}],"page":"476 - 490","volume":"34 ","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2015-06-11T00:00:00Z","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"abstract":[{"lang":"eng","text":"The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition."}],"ddc":["510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":1,"has_accepted_license":"1","title":"On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result","date_updated":"2023-02-23T12:38:00Z","oa":1,"pubrep_id":"502","alternative_title":["LIPIcs"],"status":"public","type":"conference","oa_version":"Published Version","day":"11","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"system","relation":"main_file","file_size":636735,"access_level":"open_access","content_type":"application/pdf","checksum":"0945811875351796324189312ca29e9e","file_id":"4871","file_name":"IST-2016-502-v1+1_42.pdf","date_created":"2018-12-12T10:11:18Z","date_updated":"2020-07-14T12:44:59Z"}],"conference":{"location":"Eindhoven, Netherlands","end_date":"2015-06-25","name":"SoCG: Symposium on Computational Geometry","start_date":"2015-06-22"},"month":"06","author":[{"full_name":"Goaoc, Xavier","first_name":"Xavier","last_name":"Goaoc"},{"last_name":"Mabillard","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac","first_name":"Isaac"},{"last_name":"Paták","full_name":"Paták, Pavel","first_name":"Pavel"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova","orcid":"0000-0002-3975-1683","first_name":"Zuzana","full_name":"Patakova, Zuzana"},{"last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin","first_name":"Martin"},{"last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli"}]},{"abstract":[{"lang":"eng","text":"We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest."}],"ddc":["510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published","department":[{"_id":"UlWa"}],"page":"507 - 521","quality_controlled":"1","volume":34,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2015-01-01T00:00:00Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"424"}]},"publist_id":"5665","date_created":"2018-12-11T11:52:27Z","citation":{"ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2015. Bounding Helly numbers via Betti numbers. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 507–521.","mla":"Goaoc, Xavier, et al. <i>Bounding Helly Numbers via Betti Numbers</i>. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 507–21, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.507\">10.4230/LIPIcs.SOCG.2015.507</a>.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Bounding Helly Numbers via Betti Numbers,” 34:507–21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.507\">https://doi.org/10.4230/LIPIcs.SOCG.2015.507</a>.","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Bounding Helly numbers via Betti numbers. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:507-521. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.507\">10.4230/LIPIcs.SOCG.2015.507</a>","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding Helly numbers via Betti numbers,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 507–521.","short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 507–521.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2015). Bounding Helly numbers via Betti numbers (Vol. 34, pp. 507–521). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.507\">https://doi.org/10.4230/LIPIcs.SOCG.2015.507</a>"},"acknowledgement":"PP, ZP and MT were partially supported by the Charles University Grant GAUK 421511. ZP was\r\npartially supported by the Charles University Grant SVV-2014-260103. ZP and MT were partially\r\nsupported by the ERC Advanced Grant No. 267165 and by the project CE-ITI (GACR P202/12/G061)\r\nof the Czech Science Foundation. UW was partially supported by the Swiss National Science Foundation\r\n(grants SNSF-200020-138230 and SNSF-PP00P2-138948). Part of this work was done when XG was affiliated with INRIA Nancy Grand-Est and when MT was affiliated with Institutionen för matematik, Kungliga Tekniska Högskolan, then IST Austria.","year":"2015","doi":"10.4230/LIPIcs.SOCG.2015.507","file_date_updated":"2020-07-14T12:45:00Z","_id":"1512","day":"01","oa_version":"Submitted Version","file":[{"file_id":"4794","file_name":"IST-2016-501-v1+1_46.pdf","checksum":"e6881df44d87fe0c2529c9f7b2724614","date_updated":"2020-07-14T12:45:00Z","date_created":"2018-12-12T10:10:09Z","creator":"system","relation":"main_file","file_size":633712,"content_type":"application/pdf","access_level":"open_access"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Eindhoven, Netherlands","end_date":"2015-06-25","name":"SoCG: Symposium on Computational Geometry","start_date":"2015-06-22"},"month":"01","author":[{"last_name":"Goaoc","full_name":"Goaoc, Xavier","first_name":"Xavier"},{"last_name":"Paták","full_name":"Paták, Pavel","first_name":"Pavel"},{"last_name":"Patakova","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana","first_name":"Zuzana"},{"last_name":"Tancer","orcid":"0000-0002-1191-6714","first_name":"Martin","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568"}],"alternative_title":["LIPIcs"],"type":"conference","status":"public","scopus_import":"1","has_accepted_license":"1","intvolume":"        34","title":"Bounding Helly numbers via Betti numbers","pubrep_id":"501","date_updated":"2024-02-28T12:59:37Z","oa":1,"article_processing_charge":"No","language":[{"iso":"eng"}]},{"publication_status":"published","ddc":["510"],"abstract":[{"text":"A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, . . . , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing- free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.","lang":"eng"}],"project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"publisher":"Springer","date_published":"2015-11-27T00:00:00Z","page":"99 - 110","department":[{"_id":"UlWa"}],"volume":9411,"quality_controlled":"1","acknowledgement":"The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].","year":"2015","date_created":"2018-12-11T11:52:55Z","publist_id":"5576","citation":{"ista":"Fulek R, Pelsmajer M, Schaefer M. 2015. Hanani-Tutte for radial planarity. GD: Graph Drawing and Network Visualization, LNCS, vol. 9411, 99–110.","chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity,” 9411:99–110. Springer, 2015. <a href=\"https://doi.org/10.1007/978-3-319-27261-0_9\">https://doi.org/10.1007/978-3-319-27261-0_9</a>.","mla":"Fulek, Radoslav, et al. <i>Hanani-Tutte for Radial Planarity</i>. Vol. 9411, Springer, 2015, pp. 99–110, doi:<a href=\"https://doi.org/10.1007/978-3-319-27261-0_9\">10.1007/978-3-319-27261-0_9</a>.","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. In: Vol 9411. Springer; 2015:99-110. doi:<a href=\"https://doi.org/10.1007/978-3-319-27261-0_9\">10.1007/978-3-319-27261-0_9</a>","ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,” presented at the GD: Graph Drawing and Network Visualization, Los Angeles, CA, USA, 2015, vol. 9411, pp. 99–110.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2015, pp. 99–110.","apa":"Fulek, R., Pelsmajer, M., &#38; Schaefer, M. (2015). Hanani-Tutte for radial planarity (Vol. 9411, pp. 99–110). Presented at the GD: Graph Drawing and Network Visualization, Los Angeles, CA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-319-27261-0_9\">https://doi.org/10.1007/978-3-319-27261-0_9</a>"},"ec_funded":1,"related_material":{"record":[{"status":"public","relation":"later_version","id":"1113"},{"status":"public","id":"1164","relation":"later_version"}]},"file_date_updated":"2020-07-14T12:45:03Z","_id":"1595","doi":"10.1007/978-3-319-27261-0_9","author":[{"orcid":"0000-0001-8485-1774","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"last_name":"Pelsmajer","full_name":"Pelsmajer, Michael","first_name":"Michael"},{"last_name":"Schaefer","first_name":"Marcus","full_name":"Schaefer, Marcus"}],"conference":{"end_date":"2015-09-26","location":"Los Angeles, CA, USA","start_date":"2015-09-24","name":"GD: Graph Drawing and Network Visualization"},"month":"11","oa_version":"Submitted Version","day":"27","file":[{"access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":330135,"creator":"system","date_created":"2018-12-12T10:08:36Z","date_updated":"2020-07-14T12:45:03Z","checksum":"685f91bd077a951ba067d42cce75409e","file_name":"IST-2016-594-v1+1_HTCylinder_GD_Revision.pdf","file_id":"4697"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"type":"conference","status":"public","pubrep_id":"594","oa":1,"date_updated":"2023-02-21T16:23:36Z","title":"Hanani-Tutte for radial planarity","scopus_import":1,"intvolume":"      9411","has_accepted_license":"1","language":[{"iso":"eng"}]},{"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"last_name":"Radoičić","full_name":"Radoičić, Radoš","first_name":"Radoš"}],"oa_version":"Submitted Version","day":"27","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","file":[{"checksum":"eec04f86c5921d04f025d5791db9b965","file_id":"5258","file_name":"IST-2016-595-v1+1_VerticalVisibilityGDRevision.pdf","date_created":"2018-12-12T10:17:06Z","date_updated":"2020-07-14T12:45:04Z","creator":"system","file_size":312992,"content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"conference":{"name":"GD: Graph Drawing and Network Visualization","start_date":"2015-09-24","location":"Los Angeles, CA, United States","end_date":"2015-09-26"},"month":"11","publication_identifier":{"isbn":["978-3-319-27260-3"]},"alternative_title":["LNCS"],"type":"book_chapter","status":"public","title":"Vertical visibility among parallel polygons in three dimensions","date_updated":"2022-01-28T09:20:50Z","oa":1,"pubrep_id":"595","article_processing_charge":"No","has_accepted_license":"1","intvolume":"      9411","scopus_import":"1","language":[{"iso":"eng"}],"publication":"Graph Drawing and Network Visualization","publication_status":"published","abstract":[{"lang":"eng","text":"Let C={C1,...,Cn} denote a collection of translates of a regular convex k-gon in the plane with the stacking order. The collection C forms a visibility clique if for everyi &lt; j the intersection Ci and (Ci ∩ Cj)\\⋃i&lt;l&lt;jCl =∅.elements that are stacked between them, i.e., We show that if C forms a visibility clique its size is bounded from above by O(k4) thereby improving the upper bound of 22k from the aforementioned paper. We also obtain an upper bound of 22(k/2)+2 on the size of a visibility clique for homothetes of a convex (not necessarily regular) k-gon."}],"ddc":["510"],"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"department":[{"_id":"UlWa"}],"page":"373 - 379","quality_controlled":"1","volume":9411,"publisher":"Springer Nature","date_published":"2015-11-27T00:00:00Z","citation":{"short":"R. Fulek, R. Radoičić, in:, Graph Drawing and Network Visualization, Springer Nature, 2015, pp. 373–379.","ieee":"R. Fulek and R. Radoičić, “Vertical visibility among parallel polygons in three dimensions,” in <i>Graph Drawing and Network Visualization</i>, vol. 9411, Springer Nature, 2015, pp. 373–379.","ama":"Fulek R, Radoičić R. Vertical visibility among parallel polygons in three dimensions. In: <i>Graph Drawing and Network Visualization</i>. Vol 9411. Springer Nature; 2015:373-379. doi:<a href=\"https://doi.org/10.1007/978-3-319-27261-0_31\">10.1007/978-3-319-27261-0_31</a>","mla":"Fulek, Radoslav, and Radoš Radoičić. “Vertical Visibility among Parallel Polygons in Three Dimensions.” <i>Graph Drawing and Network Visualization</i>, vol. 9411, Springer Nature, 2015, pp. 373–79, doi:<a href=\"https://doi.org/10.1007/978-3-319-27261-0_31\">10.1007/978-3-319-27261-0_31</a>.","ista":"Fulek R, Radoičić R. 2015.Vertical visibility among parallel polygons in three dimensions. In: Graph Drawing and Network Visualization. LNCS, vol. 9411, 373–379.","chicago":"Fulek, Radoslav, and Radoš Radoičić. “Vertical Visibility among Parallel Polygons in Three Dimensions.” In <i>Graph Drawing and Network Visualization</i>, 9411:373–79. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-319-27261-0_31\">https://doi.org/10.1007/978-3-319-27261-0_31</a>.","apa":"Fulek, R., &#38; Radoičić, R. (2015). Vertical visibility among parallel polygons in three dimensions. In <i>Graph Drawing and Network Visualization</i> (Vol. 9411, pp. 373–379). Los Angeles, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-319-27261-0_31\">https://doi.org/10.1007/978-3-319-27261-0_31</a>"},"date_created":"2018-12-11T11:52:56Z","publist_id":"5575","year":"2015","ec_funded":1,"file_date_updated":"2020-07-14T12:45:04Z","_id":"1596","doi":"10.1007/978-3-319-27261-0_31"},{"date_published":"2015-11-13T00:00:00Z","publisher":"Electronic Journal of Combinatorics","quality_controlled":"1","volume":22,"department":[{"_id":"UlWa"}],"project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"ddc":["514","516"],"abstract":[{"text":"The Hanani-Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident to at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.","lang":"eng"}],"external_id":{"arxiv":["1305.4519"]},"publication_status":"published","doi":"10.37236/5002","article_type":"original","_id":"1642","file_date_updated":"2020-07-14T12:45:08Z","related_material":{"record":[{"id":"10793","relation":"earlier_version","status":"public"}]},"article_number":"P4.24 ","ec_funded":1,"year":"2015","acknowledgement":"e research leading to these results has received funding fromthe People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme(FP7/2007-2013) under REA grant agreement no [291734], and ESF Eurogiga project GraDR as GAˇCRGIG/11/E023.","date_created":"2018-12-11T11:53:12Z","citation":{"ama":"Fulek R, Kynčl J, Malinovič I, Pálvölgyi D. Clustered planarity testing revisited. <i>Electronic Journal of Combinatorics</i>. 2015;22(4). doi:<a href=\"https://doi.org/10.37236/5002\">10.37236/5002</a>","ieee":"R. Fulek, J. Kynčl, I. Malinovič, and D. Pálvölgyi, “Clustered planarity testing revisited,” <i>Electronic Journal of Combinatorics</i>, vol. 22, no. 4. Electronic Journal of Combinatorics, 2015.","short":"R. Fulek, J. Kynčl, I. Malinovič, D. Pálvölgyi, Electronic Journal of Combinatorics 22 (2015).","chicago":"Fulek, Radoslav, Jan Kynčl, Igor Malinovič, and Dömötör Pálvölgyi. “Clustered Planarity Testing Revisited.” <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics, 2015. <a href=\"https://doi.org/10.37236/5002\">https://doi.org/10.37236/5002</a>.","ista":"Fulek R, Kynčl J, Malinovič I, Pálvölgyi D. 2015. Clustered planarity testing revisited. Electronic Journal of Combinatorics. 22(4), P4.24.","mla":"Fulek, Radoslav, et al. “Clustered Planarity Testing Revisited.” <i>Electronic Journal of Combinatorics</i>, vol. 22, no. 4, P4.24, Electronic Journal of Combinatorics, 2015, doi:<a href=\"https://doi.org/10.37236/5002\">10.37236/5002</a>.","apa":"Fulek, R., Kynčl, J., Malinovič, I., &#38; Pálvölgyi, D. (2015). Clustered planarity testing revisited. <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/5002\">https://doi.org/10.37236/5002</a>"},"publist_id":"5511","status":"public","type":"journal_article","month":"11","publication_identifier":{"eissn":["1077-8926"]},"file":[{"relation":"main_file","file_size":443655,"access_level":"open_access","content_type":"application/pdf","creator":"system","date_updated":"2020-07-14T12:45:08Z","date_created":"2018-12-12T10:15:03Z","checksum":"40b5920b49ee736694f59f39588ee206","file_name":"IST-2016-714-v1+1_5002-15499-3-PB.pdf","file_id":"5120"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"13","arxiv":1,"author":[{"first_name":"Radoslav","full_name":"Fulek, Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"},{"last_name":"Malinovič","first_name":"Igor","full_name":"Malinovič, Igor"},{"last_name":"Pálvölgyi","first_name":"Dömötör","full_name":"Pálvölgyi, Dömötör"}],"publication":"Electronic Journal of Combinatorics","language":[{"iso":"eng"}],"scopus_import":"1","intvolume":"        22","has_accepted_license":"1","issue":"4","article_processing_charge":"No","oa":1,"pubrep_id":"714","date_updated":"2023-02-21T16:03:02Z","title":"Clustered planarity testing revisited"},{"issue":"4","year":"2015","date_updated":"2021-01-12T06:52:30Z","oa":1,"publist_id":"5466","title":"Robust satisfiability of systems of equations","citation":{"apa":"Franek, P., &#38; Krcál, M. (2015). Robust satisfiability of systems of equations. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/2751524\">https://doi.org/10.1145/2751524</a>","ieee":"P. Franek and M. Krcál, “Robust satisfiability of systems of equations,” <i>Journal of the ACM</i>, vol. 62, no. 4. ACM, 2015.","ama":"Franek P, Krcál M. Robust satisfiability of systems of equations. <i>Journal of the ACM</i>. 2015;62(4). doi:<a href=\"https://doi.org/10.1145/2751524\">10.1145/2751524</a>","short":"P. Franek, M. Krcál, Journal of the ACM 62 (2015).","mla":"Franek, Peter, and Marek Krcál. “Robust Satisfiability of Systems of Equations.” <i>Journal of the ACM</i>, vol. 62, no. 4, 26, ACM, 2015, doi:<a href=\"https://doi.org/10.1145/2751524\">10.1145/2751524</a>.","chicago":"Franek, Peter, and Marek Krcál. “Robust Satisfiability of Systems of Equations.” <i>Journal of the ACM</i>. ACM, 2015. <a href=\"https://doi.org/10.1145/2751524\">https://doi.org/10.1145/2751524</a>.","ista":"Franek P, Krcál M. 2015. Robust satisfiability of systems of equations. Journal of the ACM. 62(4), 26."},"date_created":"2018-12-11T11:53:27Z","article_number":"26","intvolume":"        62","scopus_import":1,"_id":"1682","language":[{"iso":"eng"}],"publication":"Journal of the ACM","doi":"10.1145/2751524","author":[{"last_name":"Franek","first_name":"Peter","full_name":"Franek, Peter"},{"last_name":"Krcál","id":"33E21118-F248-11E8-B48F-1D18A9856A87","full_name":"Krcál, Marek","first_name":"Marek"}],"publication_status":"published","month":"08","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f:K→ ℝn on a finite simplicial complex K and α &gt; 0, it holds that each function g: K → ℝn such that ||g - f || ∞ &lt; α, has a root in K. Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed n, assuming dimK ≤ 2n - 3. This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis. Via a reverse reduction, we prove that the problem is undecidable when dim K &gt; 2n - 2, where the threshold comes from the stable range in homotopy theory. For the lucidity of our exposition, we focus on the setting when f is simplexwise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.","lang":"eng"}],"oa_version":"Preprint","day":"01","main_file_link":[{"url":"http://arxiv.org/abs/1402.0858","open_access":"1"}],"status":"public","date_published":"2015-08-01T00:00:00Z","type":"journal_article","publisher":"ACM","quality_controlled":"1","volume":62,"department":[{"_id":"UlWa"},{"_id":"HeEd"}]},{"page":"386 - 398","department":[{"_id":"UlWa"}],"volume":9294,"quality_controlled":"1","publisher":"Springer","date_published":"2015-09-01T00:00:00Z","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"abstract":[{"lang":"eng","text":"Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε &gt; 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3.\r\nOur techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest."}],"publication_status":"published","doi":"10.1007/978-3-662-48350-3_33","_id":"1685","ec_funded":1,"citation":{"apa":"Cohen Addad, V., &#38; de Mesmay, A. N. (2015). A fixed parameter tractable approximation scheme for the optimal cut graph of a surface (Vol. 9294, pp. 386–398). Presented at the ESA: European Symposium on Algorithms, Patras, Greece: Springer. <a href=\"https://doi.org/10.1007/978-3-662-48350-3_33\">https://doi.org/10.1007/978-3-662-48350-3_33</a>","ieee":"V. Cohen Addad and A. N. de Mesmay, “A fixed parameter tractable approximation scheme for the optimal cut graph of a surface,” presented at the ESA: European Symposium on Algorithms, Patras, Greece, 2015, vol. 9294, pp. 386–398.","ama":"Cohen Addad V, de Mesmay AN. A fixed parameter tractable approximation scheme for the optimal cut graph of a surface. In: Vol 9294. Springer; 2015:386-398. doi:<a href=\"https://doi.org/10.1007/978-3-662-48350-3_33\">10.1007/978-3-662-48350-3_33</a>","short":"V. Cohen Addad, A.N. de Mesmay, in:, Springer, 2015, pp. 386–398.","ista":"Cohen Addad V, de Mesmay AN. 2015. A fixed parameter tractable approximation scheme for the optimal cut graph of a surface. ESA: European Symposium on Algorithms, LNCS, vol. 9294, 386–398.","chicago":"Cohen Addad, Vincent, and Arnaud N de Mesmay. “A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface,” 9294:386–98. Springer, 2015. <a href=\"https://doi.org/10.1007/978-3-662-48350-3_33\">https://doi.org/10.1007/978-3-662-48350-3_33</a>.","mla":"Cohen Addad, Vincent, and Arnaud N. de Mesmay. <i>A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface</i>. Vol. 9294, Springer, 2015, pp. 386–98, doi:<a href=\"https://doi.org/10.1007/978-3-662-48350-3_33\">10.1007/978-3-662-48350-3_33</a>."},"date_created":"2018-12-11T11:53:27Z","publist_id":"5462","year":"2015","alternative_title":["LNCS"],"type":"conference","status":"public","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1507.01688"}],"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Patras, Greece","end_date":"2015-09-16","name":"ESA: European Symposium on Algorithms","start_date":"2015-09-14"},"month":"09","author":[{"first_name":"Vincent","full_name":"Cohen Addad, Vincent","last_name":"Cohen Addad"},{"first_name":"Arnaud N","full_name":"De Mesmay, Arnaud N","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","last_name":"De Mesmay"}],"language":[{"iso":"eng"}],"intvolume":"      9294","scopus_import":1,"title":"A fixed parameter tractable approximation scheme for the optimal cut graph of a surface","oa":1,"date_updated":"2021-01-12T06:52:31Z"},{"department":[{"_id":"UlWa"}],"page":"610 - 636","volume":54,"quality_controlled":"1","publisher":"Springer","date_published":"2015-10-01T00:00:00Z","publication_status":"published","abstract":[{"lang":"eng","text":"We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant (Formula presented.) such that whenever (Formula presented.) are n-element subsets of (Formula presented.), we can find a point (Formula presented.) and subsets (Formula presented.) for every i∈[d+1], each of size at least cdn, such that p belongs to all rainbowd-simplices determined by (Formula presented.) simplices with one vertex in each Yi. We show a super-exponentially decreasing upper bound (Formula presented.). The ideas used in the proof of the upper bound also help us to prove Pach’s theorem with (Formula presented.), which is a lower bound doubly exponentially decreasing in d (up to some polynomial in the exponent). For comparison, Pach’s original approach yields a triply exponentially decreasing lower bound. On the other hand, Fox, Pach, and Suk recently obtained a hypergraph density result implying a proof of Pach’s theorem with (Formula presented.). In our construction for the upper bound, we use the fact that the minimum solid angle of every d-simplex is super-exponentially small. This fact was previously unknown and might be of independent interest. For the lower bound, we improve the ‘separation’ part of the argument by showing that in one of the key steps only d+1 separations are necessary, compared to 2d separations in the original proof. We also provide a measure version of Pach’s theorem."}],"_id":"1688","doi":"10.1007/s00454-015-9720-z","publist_id":"5457","citation":{"ieee":"R. Karasev, J. Kynčl, P. Paták, Z. Patakova, and M. Tancer, “Bounds for Pach’s selection theorem and for the minimum solid angle in a simplex,” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 3. Springer, pp. 610–636, 2015.","ama":"Karasev R, Kynčl J, Paták P, Patakova Z, Tancer M. Bounds for Pach’s selection theorem and for the minimum solid angle in a simplex. <i>Discrete &#38; Computational Geometry</i>. 2015;54(3):610-636. doi:<a href=\"https://doi.org/10.1007/s00454-015-9720-z\">10.1007/s00454-015-9720-z</a>","short":"R. Karasev, J. Kynčl, P. Paták, Z. Patakova, M. Tancer, Discrete &#38; Computational Geometry 54 (2015) 610–636.","chicago":"Karasev, Roman, Jan Kynčl, Pavel Paták, Zuzana Patakova, and Martin Tancer. “Bounds for Pach’s Selection Theorem and for the Minimum Solid Angle in a Simplex.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s00454-015-9720-z\">https://doi.org/10.1007/s00454-015-9720-z</a>.","mla":"Karasev, Roman, et al. “Bounds for Pach’s Selection Theorem and for the Minimum Solid Angle in a Simplex.” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 3, Springer, 2015, pp. 610–36, doi:<a href=\"https://doi.org/10.1007/s00454-015-9720-z\">10.1007/s00454-015-9720-z</a>.","ista":"Karasev R, Kynčl J, Paták P, Patakova Z, Tancer M. 2015. Bounds for Pach’s selection theorem and for the minimum solid angle in a simplex. Discrete &#38; Computational Geometry. 54(3), 610–636.","apa":"Karasev, R., Kynčl, J., Paták, P., Patakova, Z., &#38; Tancer, M. (2015). Bounds for Pach’s selection theorem and for the minimum solid angle in a simplex. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-015-9720-z\">https://doi.org/10.1007/s00454-015-9720-z</a>"},"date_created":"2018-12-11T11:53:28Z","acknowledgement":"R. K. was supported by the Russian Foundation for Basic Research Grant 15-31-20403 (mol_a_ved) and grant 15-01-99563. J. K., Z. P., and M. T. were partially supported by ERC Advanced Research Grant No. 267165 (DISCONV) and by the project CE-ITI (GAČR P202/12/G061) of the Czech Science Foundation. J. K. was also partially supported by Swiss National Science Foundation Grants 200021-137574 and 200020-14453. P. P., Z. P., and M. T. were partially supported by the Charles University Grant GAUK 421511. P. P. was also partially supported by the Charles University Grant SVV-2014-260107. Z. P. was also partially supported by the Charles University Grant SVV-2014-260103.","year":"2015","status":"public","type":"journal_article","author":[{"first_name":"Roman","full_name":"Karasev, Roman","last_name":"Karasev"},{"first_name":"Jan","full_name":"Kynčl, Jan","last_name":"Kynčl"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"last_name":"Patakova","orcid":"0000-0002-3975-1683","first_name":"Zuzana","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","orcid":"0000-0002-1191-6714"}],"day":"01","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1403.8147"}],"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"10","language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","title":"Bounds for Pach's selection theorem and for the minimum solid angle in a simplex","oa":1,"date_updated":"2021-01-12T06:52:32Z","issue":"3","intvolume":"        54","scopus_import":1},{"page":"587 - 620","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":53,"publisher":"Springer","type":"journal_article","date_published":"2015-04-02T00:00:00Z","status":"public","day":"02","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1408.4036"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart). Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993), a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s systolic inequality for surfaces are essentially equivalent. We also discuss how these proofs generalize to higher dimensions. Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length O(g^(3/2)n^(1/2)) for any triangulated combinatorial surface of genus g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition. Finally, we consider the problem of embedding a cut graph (or more generally a cellular graph) with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of a combinatorial map, there are some surfaces on which any cellular embedding with that combinatorial map has length superlinear in the number of triangles of the triangulated combinatorial surface. There is also a similar result for graphs embedded on polyhedral triangulations."}],"month":"04","author":[{"last_name":"Colin De Verdière","full_name":"Colin De Verdière, Éric","first_name":"Éric"},{"first_name":"Alfredo","full_name":"Hubard, Alfredo","last_name":"Hubard"},{"last_name":"De Mesmay","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","first_name":"Arnaud N","full_name":"De Mesmay, Arnaud N"}],"publication_status":"published","doi":"10.1007/s00454-015-9679-9","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"_id":"1730","intvolume":"        53","scopus_import":1,"publist_id":"5397","date_created":"2018-12-11T11:53:42Z","citation":{"apa":"Colin De Verdière, É., Hubard, A., &#38; de Mesmay, A. N. (2015). Discrete systolic inequalities and decompositions of triangulated surfaces. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-015-9679-9\">https://doi.org/10.1007/s00454-015-9679-9</a>","short":"É. Colin De Verdière, A. Hubard, A.N. de Mesmay, Discrete &#38; Computational Geometry 53 (2015) 587–620.","ieee":"É. Colin De Verdière, A. Hubard, and A. N. de Mesmay, “Discrete systolic inequalities and decompositions of triangulated surfaces,” <i>Discrete &#38; Computational Geometry</i>, vol. 53, no. 3. Springer, pp. 587–620, 2015.","ama":"Colin De Verdière É, Hubard A, de Mesmay AN. Discrete systolic inequalities and decompositions of triangulated surfaces. <i>Discrete &#38; Computational Geometry</i>. 2015;53(3):587-620. doi:<a href=\"https://doi.org/10.1007/s00454-015-9679-9\">10.1007/s00454-015-9679-9</a>","mla":"Colin De Verdière, Éric, et al. “Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces.” <i>Discrete &#38; Computational Geometry</i>, vol. 53, no. 3, Springer, 2015, pp. 587–620, doi:<a href=\"https://doi.org/10.1007/s00454-015-9679-9\">10.1007/s00454-015-9679-9</a>.","ista":"Colin De Verdière É, Hubard A, de Mesmay AN. 2015. Discrete systolic inequalities and decompositions of triangulated surfaces. Discrete &#38; Computational Geometry. 53(3), 587–620.","chicago":"Colin De Verdière, Éric, Alfredo Hubard, and Arnaud N de Mesmay. “Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s00454-015-9679-9\">https://doi.org/10.1007/s00454-015-9679-9</a>."},"title":"Discrete systolic inequalities and decompositions of triangulated surfaces","oa":1,"date_updated":"2021-01-12T06:52:49Z","issue":"3","year":"2015"},{"file":[{"relation":"main_file","file_size":511233,"access_level":"open_access","content_type":"application/pdf","creator":"dernst","date_created":"2019-11-18T15:57:51Z","date_updated":"2020-07-14T12:47:48Z","file_id":"7039","checksum":"2b94e5e1f4c3fe8ab89b12806276fb09","file_name":"2014_Playful_Math_Huszar.pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"30","month":"06","ddc":["510"],"publication_status":"draft","author":[{"first_name":"Kristóf","full_name":"Huszár, Kristóf","last_name":"Huszár","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057"},{"first_name":"Michal","full_name":"Rolinek, Michal","last_name":"Rolinek","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"}],"page":"5","department":[{"_id":"VlKo"},{"_id":"UlWa"}],"date_published":"2014-06-30T00:00:00Z","status":"public","type":"working_paper","publisher":"IST Austria","has_accepted_license":"1","citation":{"ieee":"K. Huszár and M. Rolinek, <i>Playful Math - An introduction to mathematical games</i>. IST Austria.","ama":"Huszár K, Rolinek M. <i>Playful Math - An Introduction to Mathematical Games</i>. IST Austria","short":"K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games, IST Austria, n.d.","ista":"Huszár K, Rolinek M. Playful Math - An introduction to mathematical games, IST Austria, 5p.","mla":"Huszár, Kristóf, and Michal Rolinek. <i>Playful Math - An Introduction to Mathematical Games</i>. IST Austria.","chicago":"Huszár, Kristóf, and Michal Rolinek. <i>Playful Math - An Introduction to Mathematical Games</i>. IST Austria, n.d.","apa":"Huszár, K., &#38; Rolinek, M. (n.d.). <i>Playful Math - An introduction to mathematical games</i>. IST Austria."},"date_created":"2019-11-18T15:57:05Z","title":"Playful Math - An introduction to mathematical games","year":"2014","article_processing_charge":"No","oa":1,"date_updated":"2020-07-14T23:11:45Z","_id":"7038","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:48Z"},{"author":[{"first_name":"Josef","full_name":"Cibulka, Josef","last_name":"Cibulka"},{"last_name":"Gao","first_name":"Pu","full_name":"Gao, Pu"},{"last_name":"Krcál","id":"33E21118-F248-11E8-B48F-1D18A9856A87","full_name":"Krcál, Marek","first_name":"Marek"},{"first_name":"Tomáš","full_name":"Valla, Tomáš","last_name":"Valla"},{"last_name":"Valtr","first_name":"Pavel","full_name":"Valtr, Pavel"}],"publication_status":"published","abstract":[{"text":"We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n3) and O(n10), in the convex and general case, respectively. We then apply similar methods to prove an (Formula presented.) upper bound on the Ramsey number of a path with n ordered vertices.","lang":"eng"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","day":"14","oa_version":"Submitted Version","main_file_link":[{"url":"http://arxiv.org/abs/1310.7004","open_access":"1"}],"month":"11","volume":53,"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"page":"64 - 79","date_published":"2014-11-14T00:00:00Z","type":"journal_article","status":"public","publisher":"Springer","title":"On the geometric ramsey number of outerplanar graphs","publist_id":"5260","citation":{"apa":"Cibulka, J., Gao, P., Krcál, M., Valla, T., &#38; Valtr, P. (2014). On the geometric ramsey number of outerplanar graphs. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-014-9646-x\">https://doi.org/10.1007/s00454-014-9646-x</a>","ista":"Cibulka J, Gao P, Krcál M, Valla T, Valtr P. 2014. On the geometric ramsey number of outerplanar graphs. Discrete &#38; Computational Geometry. 53(1), 64–79.","chicago":"Cibulka, Josef, Pu Gao, Marek Krcál, Tomáš Valla, and Pavel Valtr. “On the Geometric Ramsey Number of Outerplanar Graphs.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00454-014-9646-x\">https://doi.org/10.1007/s00454-014-9646-x</a>.","mla":"Cibulka, Josef, et al. “On the Geometric Ramsey Number of Outerplanar Graphs.” <i>Discrete &#38; Computational Geometry</i>, vol. 53, no. 1, Springer, 2014, pp. 64–79, doi:<a href=\"https://doi.org/10.1007/s00454-014-9646-x\">10.1007/s00454-014-9646-x</a>.","short":"J. Cibulka, P. Gao, M. Krcál, T. Valla, P. Valtr, Discrete &#38; Computational Geometry 53 (2014) 64–79.","ama":"Cibulka J, Gao P, Krcál M, Valla T, Valtr P. On the geometric ramsey number of outerplanar graphs. <i>Discrete &#38; Computational Geometry</i>. 2014;53(1):64-79. doi:<a href=\"https://doi.org/10.1007/s00454-014-9646-x\">10.1007/s00454-014-9646-x</a>","ieee":"J. Cibulka, P. Gao, M. Krcál, T. Valla, and P. Valtr, “On the geometric ramsey number of outerplanar graphs,” <i>Discrete &#38; Computational Geometry</i>, vol. 53, no. 1. Springer, pp. 64–79, 2014."},"date_created":"2018-12-11T11:54:18Z","issue":"1","year":"2014","date_updated":"2021-01-12T06:53:33Z","oa":1,"acknowledgement":"Marek Krčál was supported by the ERC Advanced Grant No. 267165.","scopus_import":1,"intvolume":"        53","language":[{"iso":"eng"}],"_id":"1842","doi":"10.1007/s00454-014-9646-x","publication":"Discrete & Computational Geometry"},{"month":"01","publication_identifier":{"issn":["0302-9743"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","day":"01","arxiv":1,"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774"},{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"},{"first_name":"Igor","full_name":"Malinović, Igor","last_name":"Malinović"},{"full_name":"Pálvölgyi, Dömötör","first_name":"Dömötör","last_name":"Pálvölgyi"}],"type":"conference","status":"public","alternative_title":["LNCS"],"intvolume":"      8871","scopus_import":"1","article_processing_charge":"No","date_updated":"2023-02-23T10:08:04Z","title":"Clustered planarity testing revisited","publication":"International Symposium on Graph Drawing","language":[{"iso":"eng"}],"abstract":[{"text":"The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this classical result to clustered graphs with two disjoint clusters, and show that a straightforward extension of our result to flat clustered graphs with three or more disjoint clusters is not possible.\r\n\r\nWe also give a new and short proof for a related result by Di Battista and Frati based on the matroid intersection algorithm.","lang":"eng"}],"external_id":{"arxiv":["1305.4519"]},"place":"Cham","publication_status":"published","date_published":"2014-01-01T00:00:00Z","publisher":"Springer Nature","quality_controlled":"1","volume":8871,"page":"428-436","department":[{"_id":"UlWa"}],"related_material":{"record":[{"relation":"later_version","id":"1642","status":"public"}]},"year":"2014","citation":{"apa":"Fulek, R., Kynčl, J., Malinović, I., &#38; Pálvölgyi, D. (2014). Clustered planarity testing revisited. In <i>International Symposium on Graph Drawing</i> (Vol. 8871, pp. 428–436). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">https://doi.org/10.1007/978-3-662-45803-7_36</a>","chicago":"Fulek, Radoslav, Jan Kynčl, Igor Malinović, and Dömötör Pálvölgyi. “Clustered Planarity Testing Revisited.” In <i>International Symposium on Graph Drawing</i>, 8871:428–36. Cham: Springer Nature, 2014. <a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">https://doi.org/10.1007/978-3-662-45803-7_36</a>.","ista":"Fulek R, Kynčl J, Malinović I, Pálvölgyi D. 2014. Clustered planarity testing revisited. International Symposium on Graph Drawing. , LNCS, vol. 8871, 428–436.","mla":"Fulek, Radoslav, et al. “Clustered Planarity Testing Revisited.” <i>International Symposium on Graph Drawing</i>, vol. 8871, Springer Nature, 2014, pp. 428–36, doi:<a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">10.1007/978-3-662-45803-7_36</a>.","short":"R. Fulek, J. Kynčl, I. Malinović, D. Pálvölgyi, in:, International Symposium on Graph Drawing, Springer Nature, Cham, 2014, pp. 428–436.","ieee":"R. Fulek, J. Kynčl, I. Malinović, and D. Pálvölgyi, “Clustered planarity testing revisited,” in <i>International Symposium on Graph Drawing</i>, 2014, vol. 8871, pp. 428–436.","ama":"Fulek R, Kynčl J, Malinović I, Pálvölgyi D. Clustered planarity testing revisited. In: <i>International Symposium on Graph Drawing</i>. Vol 8871. Cham: Springer Nature; 2014:428-436. doi:<a href=\"https://doi.org/10.1007/978-3-662-45803-7_36\">10.1007/978-3-662-45803-7_36</a>"},"date_created":"2022-02-25T10:32:14Z","doi":"10.1007/978-3-662-45803-7_36","_id":"10793"},{"intvolume":"        52","scopus_import":1,"title":"On Gromov's method of selecting heavily covered points","date_updated":"2021-01-12T06:55:38Z","oa":1,"issue":"1","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"day":"01","main_file_link":[{"url":"http://arxiv.org/abs/1102.3515","open_access":"1"}],"oa_version":"Submitted Version","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","month":"07","author":[{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"full_name":"Wagner, Uli","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"type":"journal_article","status":"public","publist_id":"4852","citation":{"apa":"Matoušek, J., &#38; Wagner, U. (2014). On Gromov’s method of selecting heavily covered points. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-014-9584-7\">https://doi.org/10.1007/s00454-014-9584-7</a>","chicago":"Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered Points.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00454-014-9584-7\">https://doi.org/10.1007/s00454-014-9584-7</a>.","ista":"Matoušek J, Wagner U. 2014. On Gromov’s method of selecting heavily covered points. Discrete &#38; Computational Geometry. 52(1), 1–33.","mla":"Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered Points.” <i>Discrete &#38; Computational Geometry</i>, vol. 52, no. 1, Springer, 2014, pp. 1–33, doi:<a href=\"https://doi.org/10.1007/s00454-014-9584-7\">10.1007/s00454-014-9584-7</a>.","short":"J. Matoušek, U. Wagner, Discrete &#38; Computational Geometry 52 (2014) 1–33.","ieee":"J. Matoušek and U. Wagner, “On Gromov’s method of selecting heavily covered points,” <i>Discrete &#38; Computational Geometry</i>, vol. 52, no. 1. Springer, pp. 1–33, 2014.","ama":"Matoušek J, Wagner U. On Gromov’s method of selecting heavily covered points. <i>Discrete &#38; Computational Geometry</i>. 2014;52(1):1-33. doi:<a href=\"https://doi.org/10.1007/s00454-014-9584-7\">10.1007/s00454-014-9584-7</a>"},"date_created":"2018-12-11T11:56:01Z","acknowledgement":"Swiss National Science Foundation (SNF 200021-125309, 200020-138230, 200020-12507)","year":"2014","doi":"10.1007/s00454-014-9584-7","_id":"2154","abstract":[{"text":"A result of Boros and Füredi (d = 2) and of Bárány (arbitrary d) asserts that for every d there exists cd &gt; 0 such that for every n-point set P ⊂ ℝd, some point of ℝd is covered by at least (Formula presented.) of the d-simplices spanned by the points of P. The largest possible value of cd has been the subject of ongoing research. Recently Gromov improved the existing lower bounds considerably by introducing a new, topological proof method. We provide an exposition of the combinatorial component of Gromov's approach, in terms accessible to combinatorialists and discrete geometers, and we investigate the limits of his method. In particular, we give tighter bounds on the cofilling profiles for the (n - 1)-simplex. These bounds yield a minor improvement over Gromov's lower bounds on cd for large d, but they also show that the room for further improvement through the cofilling profiles alone is quite small. We also prove a slightly better lower bound for c3 by an approach using an additional structure besides the cofilling profiles. We formulate a combinatorial extremal problem whose solution might perhaps lead to a tight lower bound for cd.","lang":"eng"}],"publication_status":"published","department":[{"_id":"UlWa"}],"page":"1 - 33","volume":52,"quality_controlled":"1","publisher":"Springer","date_published":"2014-07-01T00:00:00Z","project":[{"grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}]}]