[{"doi":"10.1007/s00454-015-9679-9","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."}],"oa":1,"page":"587 - 620","month":"04","author":[{"full_name":"Colin De Verdière, Éric","last_name":"Colin De Verdière","first_name":"Éric"},{"first_name":"Alfredo","full_name":"Hubard, Alfredo","last_name":"Hubard"},{"first_name":"Arnaud N","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","full_name":"De Mesmay, Arnaud N","last_name":"De Mesmay"}],"date_created":"2018-12-11T11:53:42Z","publist_id":"5397","department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"UlWa"}],"language":[{"iso":"eng"}],"intvolume":" 53","status":"public","main_file_link":[{"url":"http://arxiv.org/abs/1408.4036","open_access":"1"}],"publication_status":"published","citation":{"apa":"Colin De Verdière, É., Hubard, A., & De Mesmay, A. N. (2015). Discrete systolic inequalities and decompositions of triangulated surfaces. *Discrete & Computational Geometry*, *53*(3), 587–620. https://doi.org/10.1007/s00454-015-9679-9","chicago":"Colin De Verdière, Éric, Alfredo Hubard, and Arnaud N De Mesmay. “Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces.” *Discrete & Computational Geometry* 53, no. 3 (2015): 587–620. https://doi.org/10.1007/s00454-015-9679-9.","ama":"Colin De Verdière É, Hubard A, De Mesmay AN. Discrete systolic inequalities and decompositions of triangulated surfaces. *Discrete & Computational Geometry*. 2015;53(3):587-620. doi:10.1007/s00454-015-9679-9","ista":"Colin De Verdière É, Hubard A, De Mesmay AN. 2015. Discrete systolic inequalities and decompositions of triangulated surfaces. Discrete & Computational Geometry. 53(3), 587–620.","ieee":"É. Colin De Verdière, A. Hubard, and A. N. De Mesmay, “Discrete systolic inequalities and decompositions of triangulated surfaces,” *Discrete & Computational Geometry*, vol. 53, no. 3, pp. 587–620, 2015.","mla":"Colin De Verdière, Éric, et al. “Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces.” *Discrete & Computational Geometry*, vol. 53, no. 3, Springer, 2015, pp. 587–620, doi:10.1007/s00454-015-9679-9.","short":"É. Colin De Verdière, A. Hubard, A.N. De Mesmay, Discrete & Computational Geometry 53 (2015) 587–620."},"_id":"1730","volume":53,"quality_controlled":"1","type":"journal_article","title":"Discrete systolic inequalities and decompositions of triangulated surfaces","publication":"Discrete & Computational Geometry","date_published":"2015-04-02T00:00:00Z","date_updated":"2019-01-24T13:04:22Z","issue":"3","publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","day":"02","year":"2015","_version":7,"creator":{"id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","login":"dernst"}},{"file":[{"content_type":"application/pdf","open_access":1,"file_name":"IST-2016-594-v1+1_HTCylinder_GD_Revision.pdf","file_size":330135,"date_created":"2018-12-12T10:08:36Z","date_updated":"2018-12-12T10:08:36Z","relation":"main_file","access_level":"open_access","file_id":"4697","creator":"system"}],"_id":"1595","_version":34,"year":"2015","accept":"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].","conference":{"location":"Los Angeles, CA, USA","start_date":"2015-09-24","name":"GD: Graph Drawing and Network Visualization","end_date":"2015-09-26"},"month":"11","date_created":"2018-12-11T11:52:55Z","page":"99 - 110","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. 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."}],"doi":"10.1007/978-3-319-27261-0_9","publication_status":"published","pubrep_id":"594","status":"public","file_date_updated":"2018-12-12T10:08:36Z","intvolume":" 9411","publist_id":"5576","department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"UlWa"}],"date_updated":"2020-02-19T10:23:46Z","date_published":"2015-11-27T00:00:00Z","publisher":"Springer","quality_controlled":"1","type":"conference","title":"Hanani-Tutte for radial planarity","volume":9411,"related_material":{"record":[{"id":"1164","status":"public","relation":"later_version"},{"id":"1113","status":"public","relation":"later_version"}]},"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.","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.","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. In: Vol 9411. Springer; 2015:99-110. doi:10.1007/978-3-319-27261-0_9","chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity,” 9411:99–110. Springer, 2015. https://doi.org/10.1007/978-3-319-27261-0_9.","apa":"Fulek, R., Pelsmajer, M., & 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. https://doi.org/10.1007/978-3-319-27261-0_9","short":"R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2015, pp. 99–110.","mla":"Fulek, Radoslav, et al. *Hanani-Tutte for Radial Planarity*. Vol. 9411, Springer, 2015, pp. 99–110, doi:10.1007/978-3-319-27261-0_9."},"ddc":["510"],"creator":{"login":"kschuh","id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},"project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"alternative_title":["LNCS"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","day":"27","author":[{"last_name":"Fulek","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav"},{"last_name":"Pelsmajer","full_name":"Pelsmajer, Michael","first_name":"Michael"},{"first_name":"Marcus","full_name":"Schaefer, Marcus","last_name":"Schaefer"}],"language":[{"iso":"eng"}]},{"publist_id":"4849","department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"UlWa"}],"language":[{"iso":"eng"}],"status":"public","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1402.0815"}],"publication_status":"published","doi":"10.1145/2582112.2582137","abstract":[{"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.","lang":"eng"}],"page":"78 - 84","month":"06","date_created":"2018-12-11T11:56:02Z","author":[{"last_name":"Matoušek","full_name":"Matoušek, Jiří","first_name":"Jiří"},{"last_name":"Sedgwick","full_name":"Sedgwick, Eric","first_name":"Eric"},{"first_name":"Martin","last_name":"Tancer","full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","day":"01","year":"2014","conference":{"location":"Kyoto, Japan","name":"SoCG: Symposium on Computational Geometry","start_date":"2014-06-08","end_date":"2014-06-11"},"acknowledgement":"ERC Advanced Grant No. 267165; Grant GRADR Eurogiga GIG/11/E023 (SNSF-PP00P2-138948); Swiss National Science Foundation (SNSF-200020-138230).","_version":48,"creator":{"login":"apreinsp","id":"4435EBFC-F248-11E8-B48F-1D18A9856A87"},"related_material":{"record":[{"id":"425","status":"public","relation":"later_version"}]},"citation":{"apa":"Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2014). Embeddability in the 3 sphere is decidable. In *Proceedings of the Annual Symposium on Computational Geometry* (pp. 78–84). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582137","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3 sphere is decidable. In: *Proceedings of the Annual Symposium on Computational Geometry*. ACM; 2014:78-84. doi:10.1145/2582112.2582137","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3 Sphere Is Decidable.” In *Proceedings of the Annual Symposium on Computational Geometry*, 78–84. ACM, 2014. https://doi.org/10.1145/2582112.2582137.","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.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3 sphere is decidable,” in *Proceedings of the Annual Symposium on Computational Geometry*, Kyoto, Japan, 2014, pp. 78–84.","mla":"Matoušek, Jiří, et al. “Embeddability in the 3 Sphere Is Decidable.” *Proceedings of the Annual Symposium on Computational Geometry*, ACM, 2014, pp. 78–84, doi:10.1145/2582112.2582137.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, in:, Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 78–84."},"_id":"2157","quality_controlled":"1","type":"conference","title":"Embeddability in the 3 sphere is decidable","date_published":"2014-06-01T00:00:00Z","publication":"Proceedings of the Annual Symposium on Computational Geometry","date_updated":"2020-01-21T11:55:30Z","publisher":"ACM"},{"_version":8,"acknowledgement":"The research by M. K. was supported by project GAUK 49209. The research by M. K. was also supported by project 1M0545 by the Ministry of Education of the Czech Republic and by Center of Excellence { Inst. for Theor. Comput. Sci., Prague (project P202/12/G061 of GACR). The research by U. W. was supported by the Swiss National Science Foundation (SNF Projects 200021-125309, 200020-138230, and PP00P2-138948).","article_number":"17 ","year":"2014","_id":"2184","publication_status":"published","status":"public","intvolume":" 61","department":[{"_id":"UlWa","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]},{"_id":"HeEd","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"publist_id":"4797","date_created":"2018-12-11T11:56:12Z","month":"05","abstract":[{"text":"Given topological spaces X,Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X→ Y. We consider a computational version, where X,Y are given as finite simplicial complexes, and the goal is to compute [X,Y], that is, all homotopy classes of suchmaps.We solve this problem in the stable range, where for some d ≥ 2, we have dim X ≤ 2d-2 and Y is (d-1)-connected; in particular, Y can be the d-dimensional sphere Sd. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X,Y] is known to be uncomputable for general X,Y, since for X = S1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem, where we are given a subspace A ⊂ X and a map A→ Y and ask whether it extends to a map X → Y, or computing the Z2-index-everything in the stable range. Outside the stable range, the extension problem is undecidable.","lang":"eng"}],"doi":"10.1145/2597629","creator":{"login":"apreinsp","id":"4435EBFC-F248-11E8-B48F-1D18A9856A87"},"day":"01","oa_version":"Preprint","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"ACM","date_updated":"2020-01-21T11:40:56Z","issue":"3","publication":"Journal of the ACM","date_published":"2014-05-01T00:00:00Z","title":"Computing all maps into a sphere","quality_controlled":"1","type":"journal_article","volume":61,"citation":{"ieee":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner, “Computing all maps into a sphere,” *Journal of the ACM*, vol. 61, no. 3, 2014.","ista":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2014. Computing all maps into a sphere. Journal of the ACM. 61(3), 17.","apa":"Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., & Wagner, U. (2014). Computing all maps into a sphere. *Journal of the ACM*, *61*(3). https://doi.org/10.1145/2597629","chicago":"Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner. “Computing All Maps into a Sphere.” *Journal of the ACM* 61, no. 3 (2014). https://doi.org/10.1145/2597629.","ama":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. *Journal of the ACM*. 2014;61(3). doi:10.1145/2597629","short":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Journal of the ACM 61 (2014).","mla":"Čadek, Martin, et al. “Computing All Maps into a Sphere.” *Journal of the ACM*, vol. 61, no. 3, 17, ACM, 2014, doi:10.1145/2597629."},"main_file_link":[{"url":"http://arxiv.org/abs/1105.6257","open_access":"1"}],"language":[{"iso":"eng"}],"author":[{"first_name":"Martin","last_name":"Čadek","full_name":"Čadek, Martin"},{"first_name":"Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál","full_name":"Krcál, Marek"},{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"first_name":"Francis","full_name":"Sergeraert, Francis","last_name":"Sergeraert"},{"last_name":"Vokřínek","full_name":"Vokřínek, Lukáš","first_name":"Lukáš"},{"full_name":"Wagner, Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"oa":1},{"day":"30","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["510"],"_version":3,"creator":{"login":"dernst","id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},"accept":"1","year":"2014","message":"Created for Sommercampus @ IST Austria","_id":"7038","file":[{"file_id":"7039","creator":"dernst","access_level":"open_access","relation":"main_file","date_created":"2019-11-18T15:57:51Z","file_size":511233,"date_updated":"2019-11-18T15:57:51Z","open_access":1,"file_name":"2014_Playful_Math_Huszar.pdf","success":1,"content_type":"application/pdf"}],"citation":{"short":"K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games, IST Austria, n.d.","mla":"Huszár, Kristóf, and Michal Rolinek. *Playful Math - An Introduction to Mathematical Games*. IST Austria.","ieee":"K. Huszár and M. Rolinek, *Playful Math - An introduction to mathematical games*. IST Austria.","ista":"Huszár K, Rolinek M. Playful Math - An introduction to mathematical games, IST Austria, 5p.","apa":"Huszár, K., & Rolinek, M. (n.d.). *Playful Math - An introduction to mathematical games*. IST Austria.","ama":"Huszár K, Rolinek M. *Playful Math - An Introduction to Mathematical Games*. IST Austria","chicago":"Huszár, Kristóf, and Michal Rolinek. *Playful Math - An Introduction to Mathematical Games*. IST Austria, n.d."},"publisher":"IST Austria","date_published":"2014-06-30T00:00:00Z","date_updated":"2019-11-18T15:59:07Z","title":"Playful Math - An introduction to mathematical games","type":"working_paper","file_date_updated":"2019-11-18T15:57:51Z","language":[{"iso":"eng"}],"department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"VlKo"},{"_id":"UlWa","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"publication_status":"draft","status":"public","oa":1,"article_processing_charge":"No","date_created":"2019-11-18T15:57:05Z","author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057","full_name":"Huszár, Kristóf","last_name":"Huszár","first_name":"Kristóf"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal","last_name":"Rolinek","first_name":"Michal"}],"month":"06","page":"5"},{"language":[{"iso":"eng"}],"main_file_link":[{"url":"http://arxiv.org/abs/1102.3515","open_access":"1"}],"oa":1,"author":[{"first_name":"Jiří","full_name":"Matoušek, Jiří","last_name":"Matoušek"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","day":"01","creator":{"id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","login":"apreinsp"},"project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"volume":52,"citation":{"ista":"Matoušek J, Wagner U. 2014. On Gromov’s method of selecting heavily covered points. Discrete & Computational Geometry. 52(1), 1–33.","ieee":"J. Matoušek and U. Wagner, “On Gromov’s method of selecting heavily covered points,” *Discrete & Computational Geometry*, vol. 52, no. 1, pp. 1–33, 2014.","chicago":"Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered Points.” *Discrete & Computational Geometry* 52, no. 1 (2014): 1–33. https://doi.org/10.1007/s00454-014-9584-7.","ama":"Matoušek J, Wagner U. On Gromov’s method of selecting heavily covered points. *Discrete & Computational Geometry*. 2014;52(1):1-33. doi:10.1007/s00454-014-9584-7","apa":"Matoušek, J., & Wagner, U. (2014). On Gromov’s method of selecting heavily covered points. *Discrete & Computational Geometry*, *52*(1), 1–33. https://doi.org/10.1007/s00454-014-9584-7","short":"J. Matoušek, U. Wagner, Discrete & Computational Geometry 52 (2014) 1–33.","mla":"Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered Points.” *Discrete & Computational Geometry*, vol. 52, no. 1, Springer, 2014, pp. 1–33, doi:10.1007/s00454-014-9584-7."},"date_updated":"2019-08-02T12:37:37Z","publication":"Discrete & Computational Geometry","issue":"1","date_published":"2014-07-01T00:00:00Z","publisher":"Springer","quality_controlled":"1","type":"journal_article","title":"On Gromov's method of selecting heavily covered points","intvolume":" 52","publist_id":"4852","department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"UlWa"}],"publication_status":"published","status":"public","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 > 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."}],"doi":"10.1007/s00454-014-9584-7","month":"07","date_created":"2018-12-11T11:56:01Z","page":"1 - 33","_version":9,"year":"2014","acknowledgement":"Swiss National Science Foundation (SNF 200021-125309, 200020-138230, 200020-12507)","_id":"2154"},{"author":[{"first_name":"Isaac","full_name":"Mabillard, Isaac","last_name":"Mabillard","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","first_name":"Uli"}],"oa":1,"language":[{"iso":"eng"}],"publication":"Proceedings of the Annual Symposium on Computational Geometry","date_updated":"2020-01-21T11:40:44Z","date_published":"2014-06-08T00:00:00Z","publisher":"ACM","type":"conference","quality_controlled":"1","title":"Eliminating Tverberg points, I. An analogue of the Whitney trick","citation":{"ama":"Mabillard I, Wagner U. Eliminating Tverberg points, I. An analogue of the Whitney trick. In: *Proceedings of the Annual Symposium on Computational Geometry*. ACM; 2014:171-180. doi:10.1145/2582112.2582134","chicago":"Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue of the Whitney Trick.” In *Proceedings of the Annual Symposium on Computational Geometry*, 171–80. ACM, 2014. https://doi.org/10.1145/2582112.2582134.","apa":"Mabillard, I., & Wagner, U. (2014). Eliminating Tverberg points, I. An analogue of the Whitney trick. In *Proceedings of the Annual Symposium on Computational Geometry* (pp. 171–180). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582134","ieee":"I. Mabillard and U. Wagner, “Eliminating Tverberg points, I. An analogue of the Whitney trick,” in *Proceedings of the Annual Symposium on Computational Geometry*, Kyoto, Japan, 2014, pp. 171–180.","ista":"Mabillard I, Wagner U. 2014. Eliminating Tverberg points, I. An analogue of the Whitney trick. Proceedings of the Annual Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry 171–180.","mla":"Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue of the Whitney Trick.” *Proceedings of the Annual Symposium on Computational Geometry*, ACM, 2014, pp. 171–80, doi:10.1145/2582112.2582134.","short":"I. Mabillard, U. Wagner, in:, Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 171–180."},"related_material":{"record":[{"id":"1123","status":"public","relation":"dissertation_contains"}]},"creator":{"id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","login":"apreinsp"},"ddc":["510"],"oa_version":"Submitted Version","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","day":"08","month":"06","date_created":"2018-12-11T11:56:03Z","page":"171 - 180","abstract":[{"lang":"eng","text":"Motivated by topological Tverberg-type problems, we consider multiple (double, triple, and higher multiplicity) selfintersection points of maps from finite simplicial complexes (compact polyhedra) into ℝd and study conditions under which such multiple points can be eliminated. The most classical case is that of embeddings (i.e., maps without double points) of a κ-dimensional complex K into ℝ2κ. For this problem, the work of van Kampen, Shapiro, and Wu provides an efficiently testable necessary condition for embeddability (namely, vanishing of the van Kampen ob-struction). For κ ≥ 3, the condition is also sufficient, and yields a polynomial-time algorithm for deciding embeddability: One starts with an arbitrary map f : K→ℝ2κ, which generically has finitely many double points; if k ≥ 3 and if the obstruction vanishes then one can successively remove these double points by local modifications of the map f. One of the main tools is the famous Whitney trick that permits eliminating pairs of double points of opposite intersection sign. We are interested in generalizing this approach to intersection points of higher multiplicity. We call a point y 2 ℝd an r-fold Tverberg point of a map f : Kκ →ℝd if y lies in the intersection f(σ1)∩. ∩f(σr) of the images of r pairwise disjoint simplices of K. The analogue of (non-)embeddability that we study is the problem Tverbergκ r→d: Given a κ-dimensional complex K, does it satisfy a Tverberg-type theorem with parameters r and d, i.e., does every map f : K κ → ℝd have an r-fold Tverberg point? Here, we show that for fixed r, κ and d of the form d = rm and k = (r-1)m, m ≥ 3, there is a polynomial-time algorithm for deciding this (based on the vanishing of a cohomological obstruction, as in the case of embeddings). Our main tool is an r-fold analogue of the Whitney trick: Given r pairwise disjoint simplices of K such that the intersection of their images contains two r-fold Tverberg points y+ and y- of opposite intersection sign, we can eliminate y+ and y- by a local isotopy of f. In a subsequent paper, we plan to develop this further and present a generalization of the classical Haeiger-Weber Theorem (which yields a necessary and sufficient condition for embeddability of κ-complexes into ℝd for a wider range of dimensions) to intersection points of higher multiplicity."}],"doi":"10.1145/2582112.2582134","publication_status":"published","status":"public","pubrep_id":"534","file_date_updated":"2018-12-12T10:09:12Z","publist_id":"4847","department":[{"_id":"UlWa","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"file":[{"access_level":"open_access","file_id":"4735","creator":"system","relation":"main_file","file_name":"IST-2016-534-v1+1_Eliminating_Tverberg_points_I._An_analogue_of_the_Whitney_trick.pdf","open_access":1,"date_created":"2018-12-12T10:09:12Z","file_size":914396,"date_updated":"2018-12-12T10:09:12Z","content_type":"application/pdf"}],"_id":"2159","_version":31,"year":"2014","conference":{"end_date":"2014-06-11","location":"Kyoto, Japan","name":"SoCG: Symposium on Computational Geometry","start_date":"2014-06-08"},"acknowledgement":"Swiss National Science Foundation (Project SNSF-PP00P2-138948)","accept":"1"},{"abstract":[{"lang":"eng","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."}],"oa":1,"doi":"10.1007/s00454-014-9646-x","month":"11","author":[{"full_name":"Cibulka, Josef","last_name":"Cibulka","first_name":"Josef"},{"first_name":"Pu","full_name":"Gao, Pu","last_name":"Gao"},{"first_name":"Marek","last_name":"Krcál","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Tomáš","last_name":"Valla","full_name":"Valla, Tomáš"},{"first_name":"Pavel","last_name":"Valtr","full_name":"Valtr, Pavel"}],"date_created":"2018-12-11T11:54:18Z","page":"64 - 79","language":[{"iso":"eng"}],"intvolume":" 53","publist_id":"5260","department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"UlWa"},{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"HeEd"}],"publication_status":"published","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1310.7004"}],"status":"public","volume":53,"citation":{"short":"J. Cibulka, P. Gao, M. Krcál, T. Valla, P. Valtr, Discrete & Computational Geometry 53 (2014) 64–79.","mla":"Cibulka, Josef, et al. “On the Geometric Ramsey Number of Outerplanar Graphs.” *Discrete & Computational Geometry*, vol. 53, no. 1, Springer, 2014, pp. 64–79, doi:10.1007/s00454-014-9646-x.","ieee":"J. Cibulka, P. Gao, M. Krcál, T. Valla, and P. Valtr, “On the geometric ramsey number of outerplanar graphs,” *Discrete & Computational Geometry*, vol. 53, no. 1, pp. 64–79, 2014.","ista":"Cibulka J, Gao P, Krcál M, Valla T, Valtr P. 2014. On the geometric ramsey number of outerplanar graphs. Discrete & 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.” *Discrete & Computational Geometry* 53, no. 1 (2014): 64–79. https://doi.org/10.1007/s00454-014-9646-x.","ama":"Cibulka J, Gao P, Krcál M, Valla T, Valtr P. On the geometric ramsey number of outerplanar graphs. *Discrete & Computational Geometry*. 2014;53(1):64-79. doi:10.1007/s00454-014-9646-x","apa":"Cibulka, J., Gao, P., Krcál, M., Valla, T., & Valtr, P. (2014). On the geometric ramsey number of outerplanar graphs. *Discrete & Computational Geometry*, *53*(1), 64–79. https://doi.org/10.1007/s00454-014-9646-x"},"_id":"1842","publication":"Discrete & Computational Geometry","date_published":"2014-11-14T00:00:00Z","issue":"1","date_updated":"2019-08-02T12:37:28Z","publisher":"Springer","type":"journal_article","title":"On the geometric ramsey number of outerplanar graphs","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","day":"14","creator":{"login":"apreinsp","id":"4435EBFC-F248-11E8-B48F-1D18A9856A87"},"_version":12,"year":"2014","acknowledgement":"Marek Krčál was supported by the ERC Advanced Grant No. 267165."},{"status":"public","publication_status":"published","publist_id":"4707","department":[{"_id":"UlWa","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"intvolume":" 8242","page":"472 - 483","month":"09","date_created":"2018-12-11T11:56:32Z","doi":"10.1007/978-3-319-03841-4_41","abstract":[{"lang":"eng","text":"We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a compact two-dimensional surface ℳ with boundary. Each αi and each βj is either an arc meeting the boundary of ℳ 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 αi by a self-homeomorphism of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of ℳ pointwise such that the total number of crossings of the αi 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 ℳ 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 ℳ 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. "}],"year":"2013","conference":{"end_date":"2013-09-25","location":"Bordeaux, France","name":"GD: Graph Drawing and Network Visualization","start_date":"2013-09-23"},"acknowledgement":"We would like to thank the authors of [GHR13] for mak- ing a draft of their paper available to us, and, in particular, T. Huynh for an e-mail correspondence.","_version":41,"series_title":"Lecture Notes in Computer Science","_id":"2244","main_file_link":[{"url":"http://arxiv.org/abs/1302.6475","open_access":"1"}],"language":[{"iso":"eng"}],"author":[{"last_name":"Matoušek","full_name":"Matoušek, Jiří","first_name":"Jiří"},{"full_name":"Sedgwick, Eric","last_name":"Sedgwick","first_name":"Eric"},{"first_name":"Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin","last_name":"Tancer"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","first_name":"Uli"}],"oa":1,"project":[{"grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"alternative_title":["LNCS"],"creator":{"login":"dernst","id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},"oa_version":"Preprint","external_id":{"arxiv":["1302.6475"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","type":"conference","quality_controlled":"1","title":"Untangling two systems of noncrossing curves","date_updated":"2020-01-21T11:41:22Z","date_published":"2013-09-01T00:00:00Z","publisher":"Springer","related_material":{"record":[{"relation":"later_version","id":"1411","status":"public"}]},"citation":{"apa":"Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2013). Untangling two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network Visualization, Bordeaux, France: Springer. https://doi.org/10.1007/978-3-319-03841-4_41","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. 2013;8242:472-483. doi:10.1007/978-3-319-03841-4_41","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-319-03841-4_41.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2013. Untangling two systems of noncrossing curves. 8242, 472–483.","mla":"Matoušek, Jiří, et al. *Untangling Two Systems of Noncrossing Curves*. Vol. 8242, Springer, 2013, pp. 472–83, doi:10.1007/978-3-319-03841-4_41.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483."},"volume":8242},{"_version":12,"accept":"1","conference":{"name":"STOC: Symposium on the Theory of Computing","start_date":"2013-06-01","location":"Palo Alto, CA, United States","end_date":"2013-06-04"},"year":"2013","file":[{"file_name":"IST-2016-533-v1+1_Extending_continuous_maps_polynomiality_and_undecidability.pdf","open_access":1,"date_created":"2018-12-12T10:14:29Z","file_size":447945,"date_updated":"2018-12-12T10:14:29Z","content_type":"application/pdf","access_level":"open_access","file_id":"5081","creator":"system","relation":"main_file"}],"_id":"2807","publication_status":"published","status":"public","pubrep_id":"533","file_date_updated":"2018-12-12T10:14:29Z","department":[{"_id":"UlWa","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]},{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"HeEd"}],"publist_id":"4078","date_created":"2018-12-11T11:59:42Z","month":"06","page":"595 - 604","abstract":[{"text":"We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity. The extension problem asks, given topological spaces X; Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that X and Y are represented as finite simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map. In this generality the problem is undecidable, as follows from Novikov's result from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected; informally, this means that Y has \\no holes up to dimension k-1" (a basic example of such a Y is the sphere Sk). We prove that, on the one hand, this problem is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2, we obtain an algorithm that solves the extension problem in polynomial time assuming Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides a classification of all extensions up to homotopy (continuous deformation). This relies on results of our SODA 2012 paper, and the main new ingredient is a machinery of objects with polynomial-time homology, which is a polynomial-time analog of objects with effective homology developed earlier by Sergeraert et al. We also consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where Y is a cell complex with certain rather compact encoding. We strengthen his result to #P-hardness for Y given as a simplicial complex. ","lang":"eng"}],"doi":"10.1145/2488608.2488683","ddc":["510"],"creator":{"id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","login":"dernst"},"day":"01","oa_version":"Submitted Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"ACM","date_published":"2013-06-01T00:00:00Z","publication":"45th Annual ACM Symposium on theory of computing","date_updated":"2019-08-02T12:37:51Z","title":"Extending continuous maps: Polynomiality and undecidability","type":"conference","quality_controlled":"1","citation":{"short":"M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, U. Wagner, in:, 45th Annual ACM Symposium on Theory of Computing, ACM, 2013, pp. 595–604.","mla":"Čadek, Martin, et al. “Extending Continuous Maps: Polynomiality and Undecidability.” *45th Annual ACM Symposium on Theory of Computing*, ACM, 2013, pp. 595–604, doi:10.1145/2488608.2488683.","ista":"Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. 2013. Extending continuous maps: Polynomiality and undecidability. 45th Annual ACM Symposium on theory of computing. STOC: Symposium on the Theory of Computing 595–604.","ieee":"M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, and U. Wagner, “Extending continuous maps: Polynomiality and undecidability,” in *45th Annual ACM Symposium on theory of computing*, Palo Alto, CA, United States, 2013, pp. 595–604.","chicago":"Čadek, Martin, Marek Krcál, Jiří Matoušek, Lukáš Vokřínek, and Uli Wagner. “Extending Continuous Maps: Polynomiality and Undecidability.” In *45th Annual ACM Symposium on Theory of Computing*, 595–604. ACM, 2013. https://doi.org/10.1145/2488608.2488683.","ama":"Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. Extending continuous maps: Polynomiality and undecidability. In: *45th Annual ACM Symposium on Theory of Computing*. ACM; 2013:595-604. doi:10.1145/2488608.2488683","apa":"Čadek, M., Krcál, M., Matoušek, J., Vokřínek, L., & Wagner, U. (2013). Extending continuous maps: Polynomiality and undecidability. In *45th Annual ACM Symposium on theory of computing* (pp. 595–604). Palo Alto, CA, United States: ACM. https://doi.org/10.1145/2488608.2488683"},"language":[{"iso":"eng"}],"author":[{"first_name":"Martin","last_name":"Čadek","full_name":"Čadek, Martin"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál","full_name":"Krcál, Marek","first_name":"Marek"},{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"first_name":"Lukáš","full_name":"Vokřínek, Lukáš","last_name":"Vokřínek"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli"}],"oa":1}]