[{"scopus_import":1,"date_published":"2016-06-01T00:00:00Z","_id":"1381","conference":{"location":"Medford, MA, USA","start_date":"2016-06-14","name":"SoCG: Symposium on Computational Geometry","end_date":"2016-06-17"},"date_created":"2018-12-11T11:51:41Z","author":[{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard","first_name":"Isaac","full_name":"Mabillard, Isaac"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"abstract":[{"lang":"eng","text":"Motivated by Tverberg-type problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into double-struck Rd without higher-multiplicity intersections. We focus on conditions for the existence of almost r-embeddings, i.e., maps f : K → double-struck Rd such that f(σ1) ∩ ⋯ ∩ f(σr) = ∅ whenever σ1, ..., σr are pairwise disjoint simplices of K. Generalizing the classical Haefliger-Weber embeddability criterion, we show that a well-known necessary deleted product condition for the existence of almost r-embeddings is sufficient in a suitable r-metastable range of dimensions: If rd ≥ (r + 1) dim K + 3, then there exists an almost r-embedding K → double-struck Rd if and only if there exists an equivariant map (K)Δ r → Sr Sd(r-1)-1, where (K)Δ r is the deleted r-fold product of K, the target Sd(r-1)-1 is the sphere of dimension d(r - 1) - 1, and Sr is the symmetric group. This significantly extends one of the main results of our previous paper (which treated the special case where d = rk and dim K = (r - 1)k for some k ≥ 3), and settles an open question raised there."}],"pubrep_id":"621","intvolume":"        51","publication_status":"published","date_updated":"2021-01-12T06:50:17Z","type":"conference","ddc":["510"],"year":"2016","doi":"10.4230/LIPIcs.SoCG.2016.51","language":[{"iso":"eng"}],"month":"06","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)"},"volume":51,"page":"51.1 - 51.12","oa_version":"Published Version","file":[{"date_created":"2018-12-12T10:10:06Z","date_updated":"2020-07-14T12:44:47Z","checksum":"92c0c3735fe908f8ded6e484005cb3b1","access_level":"open_access","file_size":622969,"relation":"main_file","content_type":"application/pdf","file_name":"IST-2016-621-v1+1_LIPIcs-SoCG-2016-51.pdf","file_id":"4791","creator":"system"}],"quality_controlled":"1","citation":{"short":"I. Mabillard, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2016, p. 51.1-51.12.","chicago":"Mabillard, Isaac, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the r-Metastable Range,” 51:51.1-51.12. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.51\">https://doi.org/10.4230/LIPIcs.SoCG.2016.51</a>.","ieee":"I. Mabillard and U. Wagner, “Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range,” presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA, 2016, vol. 51, p. 51.1-51.12.","apa":"Mabillard, I., &#38; Wagner, U. (2016). Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range (Vol. 51, p. 51.1-51.12). Presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.51\">https://doi.org/10.4230/LIPIcs.SoCG.2016.51</a>","mla":"Mabillard, Isaac, and Uli Wagner. <i>Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the r-Metastable Range</i>. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2016, p. 51.1-51.12, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.51\">10.4230/LIPIcs.SoCG.2016.51</a>.","ama":"Mabillard I, Wagner U. Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range. In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH; 2016:51.1-51.12. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.51\">10.4230/LIPIcs.SoCG.2016.51</a>","ista":"Mabillard I, Wagner U. 2016. Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 51.1-51.12."},"oa":1,"day":"01","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:44:47Z","status":"public","title":"Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range","department":[{"_id":"UlWa"}],"has_accepted_license":"1","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH","project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"publist_id":"5830"},{"date_created":"2018-12-11T11:51:51Z","_id":"1408","scopus_import":1,"date_published":"2016-07-01T00:00:00Z","pubrep_id":"614","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1510"}]},"author":[{"first_name":"Peter","last_name":"Franek","full_name":"Franek, Peter","id":"473294AE-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Krcál","first_name":"Marek","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87"}],"ec_funded":1,"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."}],"issue":"1","date_updated":"2023-02-23T10:02:11Z","type":"journal_article","intvolume":"        56","publication_status":"published","month":"07","language":[{"iso":"eng"}],"year":"2016","doi":"10.1007/s00454-016-9794-2","ddc":["510"],"file":[{"date_updated":"2020-07-14T12:44:53Z","date_created":"2018-12-12T10:10:55Z","checksum":"e0da023abf6b72abd8c6a8c76740d53c","access_level":"open_access","file_size":905303,"file_id":"4846","creator":"system","file_name":"IST-2016-614-v1+1_s00454-016-9794-2.pdf","relation":"main_file","content_type":"application/pdf"}],"page":"126 - 164","oa_version":"Published Version","volume":56,"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)"},"day":"01","citation":{"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.","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>.","short":"P. Franek, M. Krcál, Discrete &#38; Computational Geometry 56 (2016) 126–164.","ista":"Franek P, Krcál M. 2016. On computability and triviality of well groups. Discrete &#38; Computational Geometry. 56(1), 126–164.","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>.","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>","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>"},"oa":1,"quality_controlled":"1","publisher":"Springer","title":"On computability and triviality of well groups","has_accepted_license":"1","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:44:53Z","publication":"Discrete & Computational Geometry","article_processing_charge":"Yes (via OA deal)","publist_id":"5799","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). ","project":[{"name":"Robust invariants of Nonlinear Systems","_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"M01980"},{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}]},{"oa_version":"Preprint","volume":212,"page":"37 - 79","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1302.6475"}],"oa":1,"citation":{"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>.","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>","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.","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>.","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."},"day":"01","quality_controlled":"1","publisher":"Springer","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Untangling two systems of noncrossing curves","department":[{"_id":"UlWa"}],"publication":"Israel Journal of Mathematics","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"acknowledgement":"Supported by the ERC Adv anced Grant No. 267165. ","publist_id":"5796","_id":"1411","date_created":"2018-12-11T11:51:52Z","date_published":"2016-05-01T00:00:00Z","scopus_import":1,"related_material":{"record":[{"id":"2244","relation":"earlier_version","status":"public"}]},"issue":"1","abstract":[{"lang":"eng","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."}],"author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"full_name":"Sedgwick, Eric","last_name":"Sedgwick","first_name":"Eric"},{"first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","full_name":"Tancer, Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"type":"journal_article","date_updated":"2023-02-23T10:34:31Z","publication_status":"published","intvolume":"       212","language":[{"iso":"eng"}],"month":"05","doi":"10.1007/s11856-016-1294-9","year":"2016"},{"publisher":"Springer","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"title":"Computation of cubical Steenrod squares","status":"public","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"},{"call_identifier":"FP7","grant_number":"622033","_id":"255F06BE-B435-11E9-9278-68D0E5697425","name":"Persistent Homology - Images, Data and Maps"}],"acknowledgement":"The research conducted by both authors has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreements no. 291734 (for M. K.) and no. 622033 (for P. P.).","publist_id":"6096","oa_version":"None","page":"140 - 151","volume":9667,"alternative_title":["LNCS"],"citation":{"ista":"Krcál M, Pilarczyk P. 2016. Computation of cubical Steenrod squares. CTIC: Computational Topology in Image Context, LNCS, vol. 9667, 140–151.","apa":"Krcál, M., &#38; Pilarczyk, P. (2016). Computation of cubical Steenrod squares (Vol. 9667, pp. 140–151). Presented at the CTIC: Computational Topology in Image Context, Marseille, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">https://doi.org/10.1007/978-3-319-39441-1_13</a>","ama":"Krcál M, Pilarczyk P. Computation of cubical Steenrod squares. In: Vol 9667. Springer; 2016:140-151. doi:<a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">10.1007/978-3-319-39441-1_13</a>","mla":"Krcál, Marek, and Pawel Pilarczyk. <i>Computation of Cubical Steenrod Squares</i>. Vol. 9667, Springer, 2016, pp. 140–51, doi:<a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">10.1007/978-3-319-39441-1_13</a>.","ieee":"M. Krcál and P. Pilarczyk, “Computation of cubical Steenrod squares,” presented at the CTIC: Computational Topology in Image Context, Marseille, France, 2016, vol. 9667, pp. 140–151.","chicago":"Krcál, Marek, and Pawel Pilarczyk. “Computation of Cubical Steenrod Squares,” 9667:140–51. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">https://doi.org/10.1007/978-3-319-39441-1_13</a>.","short":"M. Krcál, P. Pilarczyk, in:, Springer, 2016, pp. 140–151."},"day":"02","quality_controlled":"1","type":"conference","date_updated":"2021-01-12T06:49:18Z","publication_status":"published","intvolume":"      9667","language":[{"iso":"eng"}],"month":"06","doi":"10.1007/978-3-319-39441-1_13","year":"2016","conference":{"location":"Marseille, France","start_date":"2016-06-15","name":"CTIC: Computational Topology in Image Context","end_date":"2016-06-17"},"_id":"1237","date_created":"2018-12-11T11:50:52Z","date_published":"2016-06-02T00:00:00Z","scopus_import":1,"author":[{"first_name":"Marek","last_name":"Krcál","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87"},{"id":"3768D56A-F248-11E8-B48F-1D18A9856A87","full_name":"Pilarczyk, Pawel","last_name":"Pilarczyk","first_name":"Pawel"}],"abstract":[{"text":"Bitmap images of arbitrary dimension may be formally perceived as unions of m-dimensional boxes aligned with respect to a rectangular grid in ℝm. Cohomology and homology groups are well known topological invariants of such sets. Cohomological operations, such as the cup product, provide higher-order algebraic topological invariants, especially important for digital images of dimension higher than 3. If such an operation is determined at the level of simplicial chains [see e.g. González-Díaz, Real, Homology, Homotopy Appl, 2003, 83-93], then it is effectively computable. However, decomposing a cubical complex into a simplicial one deleteriously affects the efficiency of such an approach. In order to avoid this overhead, a direct cubical approach was applied in [Pilarczyk, Real, Adv. Comput. Math., 2015, 253-275] for the cup product in cohomology, and implemented in the ChainCon software package [http://www.pawelpilarczyk.com/chaincon/]. We establish a formula for the Steenrod square operations [see Steenrod, Annals of Mathematics. Second Series, 1947, 290-320] directly at the level of cubical chains, and we prove the correctness of this formula. An implementation of this formula is programmed in C++ within the ChainCon software framework. We provide a few examples and discuss the effectiveness of this approach. One specific application follows from the fact that Steenrod squares yield tests for the topological extension problem: Can a given map A → Sd to a sphere Sd be extended to a given super-complex X of A? In particular, the ROB-SAT problem, which is to decide for a given function f: X → ℝm and a value r &gt; 0 whether every g: X → ℝm with ∥g - f ∥∞ ≤ r has a root, reduces to the extension problem.","lang":"eng"}],"ec_funded":1},{"publication":"Israel Journal of Mathematics","month":"10","language":[{"iso":"eng"}],"doi":"10.1007/s11856-016-1419-1","publist_id":"6034","year":"2016","publisher":"Springer","type":"journal_article","date_updated":"2021-01-12T06:49:36Z","publication_status":"published","status":"public","intvolume":"       216","department":[{"_id":"UlWa"}],"title":"On eigenvalues of random complexes","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","day":"01","oa":1,"citation":{"chicago":"Gundert, Anna, and Uli Wagner. “On Eigenvalues of Random Complexes.” <i>Israel Journal of Mathematics</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s11856-016-1419-1\">https://doi.org/10.1007/s11856-016-1419-1</a>.","ieee":"A. Gundert and U. Wagner, “On eigenvalues of random complexes,” <i>Israel Journal of Mathematics</i>, vol. 216, no. 2. Springer, pp. 545–582, 2016.","short":"A. Gundert, U. Wagner, Israel Journal of Mathematics 216 (2016) 545–582.","ista":"Gundert A, Wagner U. 2016. On eigenvalues of random complexes. Israel Journal of Mathematics. 216(2), 545–582.","apa":"Gundert, A., &#38; Wagner, U. (2016). On eigenvalues of random complexes. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-016-1419-1\">https://doi.org/10.1007/s11856-016-1419-1</a>","mla":"Gundert, Anna, and Uli Wagner. “On Eigenvalues of Random Complexes.” <i>Israel Journal of Mathematics</i>, vol. 216, no. 2, Springer, 2016, pp. 545–82, doi:<a href=\"https://doi.org/10.1007/s11856-016-1419-1\">10.1007/s11856-016-1419-1</a>.","ama":"Gundert A, Wagner U. On eigenvalues of random complexes. <i>Israel Journal of Mathematics</i>. 2016;216(2):545-582. doi:<a href=\"https://doi.org/10.1007/s11856-016-1419-1\">10.1007/s11856-016-1419-1</a>"},"abstract":[{"lang":"eng","text":"We consider higher-dimensional generalizations of the normalized Laplacian and the adjacency matrix of graphs and study their eigenvalues for the Linial–Meshulam model Xk(n, p) of random k-dimensional simplicial complexes on n vertices. We show that for p = Ω(logn/n), the eigenvalues of each of the matrices are a.a.s. concentrated around two values. The main tool, which goes back to the work of Garland, are arguments that relate the eigenvalues of these matrices to those of graphs that arise as links of (k - 2)-dimensional faces. Garland’s result concerns the Laplacian; we develop an analogous result for the adjacency matrix. The same arguments apply to other models of random complexes which allow for dependencies between the choices of k-dimensional simplices. In the second part of the paper, we apply this to the question of possible higher-dimensional analogues of the discrete Cheeger inequality, which in the classical case of graphs relates the eigenvalues of a graph and its edge expansion. It is very natural to ask whether this generalizes to higher dimensions and, in particular, whether the eigenvalues of the higher-dimensional Laplacian capture the notion of coboundary expansion—a higher-dimensional generalization of edge expansion that arose in recent work of Linial and Meshulam and of Gromov; this question was raised, for instance, by Dotterrer and Kahle. We show that this most straightforward version of a higher-dimensional discrete Cheeger inequality fails, in quite a strong way: For every k ≥ 2 and n ∈ N, there is a k-dimensional complex Yn k on n vertices that has strong spectral expansion properties (all nontrivial eigenvalues of the normalised k-dimensional Laplacian lie in the interval [1−O(1/√1), 1+0(1/√1]) but whose coboundary expansion is bounded from above by O(log n/n) and so tends to zero as n → ∞; moreover, Yn k can be taken to have vanishing integer homology in dimension less than k."}],"author":[{"full_name":"Gundert, Anna","last_name":"Gundert","first_name":"Anna"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568"}],"quality_controlled":"1","issue":"2","date_created":"2018-12-11T11:51:07Z","oa_version":"Preprint","page":"545 - 582","volume":216,"_id":"1282","date_published":"2016-10-01T00:00:00Z","scopus_import":1,"main_file_link":[{"url":"https://arxiv.org/abs/1411.4906","open_access":"1"}]},{"external_id":{"arxiv":["1511.03501"]},"acknowledgement":"We would like to thank A. Klyachko, V. Krushkal, S. Melikhov, M. Tancer, P. Teichner and anonymous referees for helpful discussions.","year":"2015","language":[{"iso":"eng"}],"article_processing_charge":"No","publication":"arXiv","month":"11","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"submitted","title":"Eliminating higher-multiplicity intersections, III. Codimension 2","status":"public","department":[{"_id":"UlWa"}],"arxiv":1,"type":"preprint","date_updated":"2023-09-07T13:12:17Z","author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov","full_name":"Avvakumov, Sergey"},{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac","first_name":"Isaac","last_name":"Mabillard"},{"last_name":"Skopenkov","first_name":"A.","full_name":"Skopenkov, A."},{"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":"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."}],"related_material":{"record":[{"id":"9308","status":"public","relation":"later_version"},{"id":"10220","relation":"later_version","status":"public"},{"status":"public","relation":"dissertation_contains","id":"8156"}]},"oa":1,"citation":{"ista":"Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv, 1511.03501.","apa":"Avvakumov, S., Mabillard, I., Skopenkov, A., &#38; Wagner, U. (n.d.). Eliminating higher-multiplicity intersections, III. Codimension 2. <i>arXiv</i>.","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>ArXiv</i>, 1511.03501.","ama":"Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. <i>arXiv</i>.","chicago":"Avvakumov, Sergey, Isaac Mabillard, A. Skopenkov, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>ArXiv</i>, n.d.","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.)."},"article_number":"1511.03501","day":"15","main_file_link":[{"url":"https://arxiv.org/abs/1511.03501","open_access":"1"}],"date_published":"2015-11-15T00:00:00Z","oa_version":"Preprint","_id":"8183","date_created":"2020-07-30T10:45:19Z"},{"project":[{"grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme"}],"external_id":{"arxiv":["1305.4519"]},"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.","publist_id":"5511","article_processing_charge":"No","publication":"Electronic Journal of Combinatorics","file_date_updated":"2020-07-14T12:45:08Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","department":[{"_id":"UlWa"}],"title":"Clustered planarity testing revisited","has_accepted_license":"1","publisher":"Electronic Journal of Combinatorics","publication_identifier":{"eissn":["1077-8926"]},"quality_controlled":"1","oa":1,"citation":{"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.","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>","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>","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>.","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)."},"article_number":"P4.24 ","day":"13","oa_version":"Published Version","volume":22,"article_type":"original","file":[{"access_level":"open_access","checksum":"40b5920b49ee736694f59f39588ee206","date_created":"2018-12-12T10:15:03Z","date_updated":"2020-07-14T12:45:08Z","file_name":"IST-2016-714-v1+1_5002-15499-3-PB.pdf","content_type":"application/pdf","relation":"main_file","creator":"system","file_id":"5120","file_size":443655}],"ddc":["514","516"],"doi":"10.37236/5002","year":"2015","language":[{"iso":"eng"}],"month":"11","publication_status":"published","intvolume":"        22","type":"journal_article","arxiv":1,"date_updated":"2023-02-21T16:03:02Z","issue":"4","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":"Kynčl","full_name":"Kynčl, Jan"},{"full_name":"Malinovič, Igor","last_name":"Malinovič","first_name":"Igor"},{"first_name":"Dömötör","last_name":"Pálvölgyi","full_name":"Pálvölgyi, Dömötör"}],"abstract":[{"lang":"eng","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."}],"ec_funded":1,"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"10793"}]},"pubrep_id":"714","date_published":"2015-11-13T00:00:00Z","scopus_import":"1","_id":"1642","date_created":"2018-12-11T11:53:12Z"},{"type":"journal_article","date_updated":"2021-01-12T06:52:30Z","publisher":"ACM","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","title":"Robust satisfiability of systems of equations","status":"public","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"intvolume":"        62","language":[{"iso":"eng"}],"publication":"Journal of the ACM","month":"08","doi":"10.1145/2751524","publist_id":"5466","year":"2015","oa_version":"Preprint","volume":62,"_id":"1682","date_created":"2018-12-11T11:53:27Z","main_file_link":[{"url":"http://arxiv.org/abs/1402.0858","open_access":"1"}],"date_published":"2015-08-01T00:00:00Z","scopus_import":1,"oa":1,"citation":{"short":"P. Franek, M. Krcál, Journal of the ACM 62 (2015).","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>.","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.","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>.","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>","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>","ista":"Franek P, Krcál M. 2015. Robust satisfiability of systems of equations. Journal of the ACM. 62(4), 26."},"article_number":"26","day":"01","issue":"4","abstract":[{"lang":"eng","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."}],"quality_controlled":"1","author":[{"full_name":"Franek, Peter","last_name":"Franek","first_name":"Peter"},{"full_name":"Krcál, Marek","last_name":"Krcál","first_name":"Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87"}]},{"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>","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>.","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>","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.","short":"V. Cohen Addad, A.N. de Mesmay, in:, Springer, 2015, pp. 386–398.","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.","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>."},"oa":1,"day":"01","quality_controlled":"1","volume":9294,"oa_version":"Preprint","page":"386 - 398","alternative_title":["LNCS"],"main_file_link":[{"url":"http://arxiv.org/abs/1507.01688","open_access":"1"}],"project":[{"name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734"}],"publist_id":"5462","publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"UlWa"}],"title":"A fixed parameter tractable approximation scheme for the optimal cut graph of a surface","status":"public","author":[{"first_name":"Vincent","last_name":"Cohen Addad","full_name":"Cohen Addad, Vincent"},{"id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","full_name":"De Mesmay, Arnaud N","last_name":"De Mesmay","first_name":"Arnaud N"}],"abstract":[{"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.","lang":"eng"}],"ec_funded":1,"_id":"1685","conference":{"start_date":"2015-09-14","location":"Patras, Greece","name":"ESA: European Symposium on Algorithms","end_date":"2015-09-16"},"date_created":"2018-12-11T11:53:27Z","scopus_import":1,"date_published":"2015-09-01T00:00:00Z","language":[{"iso":"eng"}],"month":"09","year":"2015","doi":"10.1007/978-3-662-48350-3_33","date_updated":"2021-01-12T06:52:31Z","type":"conference","intvolume":"      9294","publication_status":"published"},{"abstract":[{"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.","lang":"eng"}],"author":[{"full_name":"Karasev, Roman","first_name":"Roman","last_name":"Karasev"},{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"},{"first_name":"Pavel","last_name":"Paták","full_name":"Paták, Pavel"},{"full_name":"Patakova, Zuzana","first_name":"Zuzana","last_name":"Patakova","orcid":"0000-0002-3975-1683"},{"first_name":"Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"}],"issue":"3","scopus_import":1,"date_published":"2015-10-01T00:00:00Z","date_created":"2018-12-11T11:53:28Z","_id":"1688","year":"2015","doi":"10.1007/s00454-015-9720-z","month":"10","language":[{"iso":"eng"}],"intvolume":"        54","publication_status":"published","date_updated":"2021-01-12T06:52:32Z","type":"journal_article","quality_controlled":"1","day":"01","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.","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>.","short":"R. Karasev, J. Kynčl, P. Paták, Z. Patakova, M. Tancer, Discrete &#38; Computational Geometry 54 (2015) 610–636.","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>","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>","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>."},"oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1403.8147"}],"page":"610 - 636","volume":54,"oa_version":"Preprint","publist_id":"5457","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.","publication":"Discrete & Computational Geometry","title":"Bounds for Pach's selection theorem and for the minimum solid angle in a simplex","status":"public","department":[{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer"},{"language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","month":"04","doi":"10.1007/s00454-015-9679-9","year":"2015","publist_id":"5397","type":"journal_article","date_updated":"2021-01-12T06:52:49Z","publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","intvolume":"        53","department":[{"_id":"UlWa"}],"title":"Discrete systolic inequalities and decompositions of triangulated surfaces","status":"public","oa":1,"citation":{"short":"É. Colin De Verdière, A. Hubard, A.N. de Mesmay, Discrete &#38; Computational Geometry 53 (2015) 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>.","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.","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>","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>.","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>","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."},"day":"02","issue":"3","author":[{"full_name":"Colin De Verdière, Éric","last_name":"Colin De Verdière","first_name":"Éric"},{"full_name":"Hubard, Alfredo","last_name":"Hubard","first_name":"Alfredo"},{"id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","full_name":"De Mesmay, Arnaud N","last_name":"De Mesmay","first_name":"Arnaud N"}],"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."}],"quality_controlled":"1","page":"587 - 620","volume":53,"oa_version":"Preprint","_id":"1730","date_created":"2018-12-11T11:53:42Z","main_file_link":[{"url":"http://arxiv.org/abs/1408.4036","open_access":"1"}],"date_published":"2015-04-02T00:00:00Z","scopus_import":1},{"intvolume":"        34","publication_status":"published","date_updated":"2023-02-21T17:02:57Z","type":"conference","ddc":["510"],"year":"2015","doi":"10.4230/LIPIcs.SOCG.2015.842","language":[{"iso":"eng"}],"month":"06","scopus_import":1,"date_published":"2015-06-11T00:00:00Z","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2015-06-25","location":"Eindhoven, Netherlands","start_date":"2015-06-22"},"_id":"1510","date_created":"2018-12-11T11:52:26Z","author":[{"full_name":"Franek, Peter","last_name":"Franek","first_name":"Peter","id":"473294AE-F248-11E8-B48F-1D18A9856A87"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Krcál","full_name":"Krcál, Marek"}],"ec_funded":1,"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"}],"related_material":{"record":[{"id":"1408","status":"public","relation":"later_version"}]},"pubrep_id":"503","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:44:59Z","has_accepted_license":"1","title":"On computability and triviality of well groups","status":"public","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme"}],"publist_id":"5667","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)"},"volume":34,"page":"842 - 856","oa_version":"Published Version","file":[{"date_created":"2018-12-12T10:13:19Z","date_updated":"2020-07-14T12:44:59Z","access_level":"open_access","checksum":"49eb5021caafaabe5356c65b9c5f8c9c","file_size":623563,"content_type":"application/pdf","relation":"main_file","file_name":"IST-2016-503-v1+1_32.pdf","file_id":"5001","creator":"system"}],"quality_controlled":"1","citation":{"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.","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>.","short":"P. Franek, M. Krcál, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 842–856.","ista":"Franek P, Krcál M. 2015. On computability and triviality of well groups. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 842–856.","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>.","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>","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>"},"oa":1,"day":"11"},{"publication_status":"published","date_updated":"2023-02-23T12:38:00Z","type":"conference","year":"2015","doi":"10.4230/LIPIcs.SOCG.2015.476","ddc":["510"],"month":"06","language":[{"iso":"eng"}],"scopus_import":1,"date_published":"2015-06-11T00:00:00Z","date_created":"2018-12-11T11:52:27Z","conference":{"location":"Eindhoven, Netherlands","start_date":"2015-06-22","name":"SoCG: Symposium on Computational Geometry","end_date":"2015-06-25"},"_id":"1511","ec_funded":1,"author":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","first_name":"Isaac","last_name":"Mabillard","full_name":"Mabillard, Isaac"},{"first_name":"Pavel","last_name":"Paták","full_name":"Paták, Pavel"},{"orcid":"0000-0002-3975-1683","last_name":"Patakova","first_name":"Zuzana","full_name":"Patakova, Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin","first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"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.","lang":"eng"}],"pubrep_id":"502","related_material":{"record":[{"status":"public","relation":"later_version","id":"610"}]},"title":"On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result","status":"public","department":[{"_id":"UlWa"}],"has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:44:59Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publist_id":"5666","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).","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"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":[{"date_updated":"2020-07-14T12:44:59Z","date_created":"2018-12-12T10:11:18Z","access_level":"open_access","checksum":"0945811875351796324189312ca29e9e","file_size":636735,"file_id":"4871","creator":"system","content_type":"application/pdf","relation":"main_file","file_name":"IST-2016-502-v1+1_42.pdf"}],"oa_version":"Published Version","volume":"34 ","page":"476 - 490","quality_controlled":"1","day":"11","citation":{"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.","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>.","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.","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.","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>","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>.","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>"},"oa":1},{"quality_controlled":"1","day":"01","oa":1,"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>.","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>","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>","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>.","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."},"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":[{"date_updated":"2020-07-14T12:45:00Z","date_created":"2018-12-12T10:10:09Z","access_level":"open_access","checksum":"e6881df44d87fe0c2529c9f7b2724614","file_size":633712,"creator":"system","file_id":"4794","file_name":"IST-2016-501-v1+1_46.pdf","relation":"main_file","content_type":"application/pdf"}],"volume":34,"oa_version":"Submitted Version","page":"507 - 521","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.","publist_id":"5665","article_processing_charge":"No","has_accepted_license":"1","status":"public","title":"Bounding Helly numbers via Betti numbers","department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:45:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"full_name":"Goaoc, Xavier","first_name":"Xavier","last_name":"Goaoc"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"full_name":"Patakova, Zuzana","first_name":"Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova"},{"full_name":"Tancer, Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714","first_name":"Martin"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","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."}],"pubrep_id":"501","related_material":{"record":[{"id":"424","relation":"later_version","status":"public"}]},"date_published":"2015-01-01T00:00:00Z","scopus_import":"1","date_created":"2018-12-11T11:52:27Z","conference":{"start_date":"2015-06-22","location":"Eindhoven, Netherlands","name":"SoCG: Symposium on Computational Geometry","end_date":"2015-06-25"},"_id":"1512","doi":"10.4230/LIPIcs.SOCG.2015.507","year":"2015","ddc":["510"],"month":"01","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"        34","type":"conference","date_updated":"2024-02-28T12:59:37Z"},{"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:45:03Z","has_accepted_license":"1","title":"Hanani-Tutte for radial planarity","status":"public","department":[{"_id":"UlWa"}],"publisher":"Springer","project":[{"name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734"}],"publist_id":"5576","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].","alternative_title":["LNCS"],"page":"99 - 110","volume":9411,"oa_version":"Submitted Version","file":[{"file_size":330135,"content_type":"application/pdf","relation":"main_file","file_name":"IST-2016-594-v1+1_HTCylinder_GD_Revision.pdf","file_id":"4697","creator":"system","date_created":"2018-12-12T10:08:36Z","date_updated":"2020-07-14T12:45:03Z","access_level":"open_access","checksum":"685f91bd077a951ba067d42cce75409e"}],"quality_controlled":"1","citation":{"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.","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>.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2015, pp. 99–110.","ista":"Fulek R, Pelsmajer M, Schaefer M. 2015. Hanani-Tutte for radial planarity. GD: Graph Drawing and Network Visualization, LNCS, vol. 9411, 99–110.","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>","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>.","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>"},"oa":1,"day":"27","intvolume":"      9411","publication_status":"published","date_updated":"2023-02-21T16:23:36Z","type":"conference","ddc":["510"],"year":"2015","doi":"10.1007/978-3-319-27261-0_9","language":[{"iso":"eng"}],"month":"11","scopus_import":1,"date_published":"2015-11-27T00:00:00Z","conference":{"start_date":"2015-09-24","location":"Los Angeles, CA, USA","name":"GD: Graph Drawing and Network Visualization","end_date":"2015-09-26"},"_id":"1595","date_created":"2018-12-11T11:52:55Z","author":[{"orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav","full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pelsmajer, Michael","last_name":"Pelsmajer","first_name":"Michael"},{"first_name":"Marcus","last_name":"Schaefer","full_name":"Schaefer, Marcus"}],"ec_funded":1,"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"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"1113"},{"id":"1164","status":"public","relation":"later_version"}]},"pubrep_id":"594"},{"quality_controlled":"1","publication_identifier":{"isbn":["978-3-319-27260-3"]},"day":"27","oa":1,"citation":{"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>","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.","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.","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>."},"alternative_title":["LNCS"],"file":[{"date_created":"2018-12-12T10:17:06Z","date_updated":"2020-07-14T12:45:04Z","checksum":"eec04f86c5921d04f025d5791db9b965","access_level":"open_access","file_size":312992,"content_type":"application/pdf","relation":"main_file","file_name":"IST-2016-595-v1+1_VerticalVisibilityGDRevision.pdf","creator":"system","file_id":"5258"}],"volume":9411,"oa_version":"Submitted Version","page":"373 - 379","publist_id":"5575","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"publication":"Graph Drawing and Network Visualization","article_processing_charge":"No","status":"public","department":[{"_id":"UlWa"}],"title":"Vertical visibility among parallel polygons in three dimensions","has_accepted_license":"1","file_date_updated":"2020-07-14T12:45:04Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publisher":"Springer Nature","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Radoičić, Radoš","first_name":"Radoš","last_name":"Radoičić"}],"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."}],"ec_funded":1,"pubrep_id":"595","date_published":"2015-11-27T00:00:00Z","scopus_import":"1","date_created":"2018-12-11T11:52:56Z","conference":{"name":"GD: Graph Drawing and Network Visualization","end_date":"2015-09-26","location":"Los Angeles, CA, United States","start_date":"2015-09-24"},"_id":"1596","doi":"10.1007/978-3-319-27261-0_31","year":"2015","ddc":["510"],"month":"11","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"      9411","type":"book_chapter","date_updated":"2022-01-28T09:20:50Z"},{"date_published":"2014-01-01T00:00:00Z","scopus_import":"1","_id":"10793","date_created":"2022-02-25T10:32:14Z","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"}],"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"},{"full_name":"Malinović, Igor","first_name":"Igor","last_name":"Malinović"},{"full_name":"Pálvölgyi, Dömötör","first_name":"Dömötör","last_name":"Pálvölgyi"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"1642"}]},"place":"Cham","publication_status":"published","intvolume":"      8871","type":"conference","arxiv":1,"date_updated":"2023-02-23T10:08:04Z","doi":"10.1007/978-3-662-45803-7_36","year":"2014","language":[{"iso":"eng"}],"month":"01","alternative_title":["LNCS"],"oa_version":"Preprint","page":"428-436","volume":8871,"publication_identifier":{"issn":["0302-9743"]},"quality_controlled":"1","citation":{"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.","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>","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>.","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>","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.","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>.","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."},"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Clustered planarity testing revisited","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","external_id":{"arxiv":["1305.4519"]},"article_processing_charge":"No","publication":"International Symposium on Graph Drawing"},{"publist_id":"5260","year":"2014","acknowledgement":"Marek Krčál was supported by the ERC Advanced Grant No. 267165.","doi":"10.1007/s00454-014-9646-x","publication":"Discrete & Computational Geometry","month":"11","language":[{"iso":"eng"}],"status":"public","intvolume":"        53","title":"On the geometric ramsey number of outerplanar graphs","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"publication_status":"published","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","date_updated":"2021-01-12T06:53:33Z","type":"journal_article","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"}],"author":[{"last_name":"Cibulka","first_name":"Josef","full_name":"Cibulka, Josef"},{"full_name":"Gao, Pu","last_name":"Gao","first_name":"Pu"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","full_name":"Krcál, Marek","last_name":"Krcál","first_name":"Marek"},{"full_name":"Valla, Tomáš","last_name":"Valla","first_name":"Tomáš"},{"full_name":"Valtr, Pavel","first_name":"Pavel","last_name":"Valtr"}],"issue":"1","day":"14","citation":{"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>","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>.","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.","short":"J. Cibulka, P. Gao, M. Krcál, T. Valla, P. Valtr, Discrete &#38; Computational Geometry 53 (2014) 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>.","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."},"oa":1,"scopus_import":1,"date_published":"2014-11-14T00:00:00Z","main_file_link":[{"url":"http://arxiv.org/abs/1310.7004","open_access":"1"}],"date_created":"2018-12-11T11:54:18Z","_id":"1842","volume":53,"oa_version":"Submitted Version","page":"64 - 79"},{"language":[{"iso":"eng"}],"month":"07","year":"2014","doi":"10.1007/s00454-014-9584-7","date_updated":"2021-01-12T06:55:38Z","type":"journal_article","intvolume":"        52","publication_status":"published","issue":"1","author":[{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"lang":"eng","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."}],"_id":"2154","date_created":"2018-12-11T11:56:01Z","scopus_import":1,"date_published":"2014-07-01T00:00:00Z","publication":"Discrete & Computational Geometry","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948"}],"publist_id":"4852","acknowledgement":"Swiss National Science Foundation (SNF 200021-125309, 200020-138230, 200020-12507)","publisher":"Springer","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","title":"On Gromov's method of selecting heavily covered points","department":[{"_id":"UlWa"}],"status":"public","citation":{"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>.","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>","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>","ista":"Matoušek J, Wagner U. 2014. On Gromov’s method of selecting heavily covered points. Discrete &#38; Computational Geometry. 52(1), 1–33.","short":"J. Matoušek, U. Wagner, Discrete &#38; Computational Geometry 52 (2014) 1–33.","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>.","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."},"oa":1,"day":"01","quality_controlled":"1","volume":52,"page":"1 - 33","oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1102.3515"}]},{"scopus_import":1,"date_published":"2014-06-01T00:00:00Z","main_file_link":[{"url":"http://arxiv.org/abs/1402.0815","open_access":"1"}],"date_created":"2018-12-11T11:56:02Z","_id":"2157","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2014-06-11","start_date":"2014-06-08","location":"Kyoto, Japan"},"page":"78 - 84","oa_version":"Submitted Version","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 ℝ3? 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, i.e., an essential curve in the boundary of X bounding a disk in S3 nX with length bounded by a computable function of the number of tetrahedra of X."}],"quality_controlled":"1","author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"last_name":"Sedgwick","first_name":"Eric","full_name":"Sedgwick, Eric"},{"full_name":"Tancer, Martin","first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli"}],"day":"01","citation":{"ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2014. Embeddability in the 3 sphere is decidable. Proceedings of the Annual Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, 78–84.","mla":"Matoušek, Jiří, et al. “Embeddability in the 3 Sphere Is Decidable.” <i>Proceedings of the Annual Symposium on Computational Geometry</i>, ACM, 2014, pp. 78–84, doi:<a href=\"https://doi.org/10.1145/2582112.2582137\">10.1145/2582112.2582137</a>.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3 sphere is decidable. In: <i>Proceedings of the Annual Symposium on Computational Geometry</i>. ACM; 2014:78-84. doi:<a href=\"https://doi.org/10.1145/2582112.2582137\">10.1145/2582112.2582137</a>","apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2014). Embeddability in the 3 sphere is decidable. In <i>Proceedings of the Annual Symposium on Computational Geometry</i> (pp. 78–84). Kyoto, Japan: ACM. <a href=\"https://doi.org/10.1145/2582112.2582137\">https://doi.org/10.1145/2582112.2582137</a>","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3 sphere is decidable,” in <i>Proceedings of the Annual Symposium on Computational Geometry</i>, Kyoto, Japan, 2014, pp. 78–84.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3 Sphere Is Decidable.” In <i>Proceedings of the Annual Symposium on Computational Geometry</i>, 78–84. ACM, 2014. <a href=\"https://doi.org/10.1145/2582112.2582137\">https://doi.org/10.1145/2582112.2582137</a>.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, in:, Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 78–84."},"oa":1,"related_material":{"record":[{"relation":"later_version","status":"public","id":"425"}]},"status":"public","title":"Embeddability in the 3 sphere is decidable","department":[{"_id":"UlWa"}],"publication_status":"published","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"ACM","date_updated":"2023-09-11T13:38:49Z","type":"conference","publist_id":"4849","year":"2014","doi":"10.1145/2582112.2582137","acknowledgement":"ERC Advanced Grant No. 267165; Grant GRADR Eurogiga GIG/11/E023  (SNSF-PP00P2-138948); Swiss National Science Foundation  (SNSF-200020-138230).","publication":"Proceedings of the Annual Symposium on Computational Geometry","month":"06","language":[{"iso":"eng"}]}]