[{"ddc":["514","516"],"volume":195,"external_id":{"isi":["000437122700017"]},"isi":1,"year":"2018","citation":{"ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. <i>Geometriae Dedicata</i>. 2018;195(1):307–317. doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>","apa":"Dotterrer, D., Kaufman, T., &#38; Wagner, U. (2018). On expansion and topological overlap. <i>Geometriae Dedicata</i>. Springer. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” <i>Geometriae Dedicata</i>, vol. 195, no. 1. Springer, pp. 307–317, 2018.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>.","short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","mla":"Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>.","ista":"Dotterrer D, Kaufman T, Wagner U. 2018. On expansion and topological overlap. Geometriae Dedicata. 195(1), 307–317."},"date_updated":"2023-09-27T12:29:57Z","abstract":[{"lang":"eng","text":"We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M."}],"day":"01","doi":"10.1007/s10711-017-0291-4","file_date_updated":"2020-07-14T12:47:58Z","quality_controlled":"1","page":"307–317","publisher":"Springer","issue":"1","author":[{"last_name":"Dotterrer","first_name":"Dominic","full_name":"Dotterrer, Dominic"},{"full_name":"Kaufman, Tali","first_name":"Tali","last_name":"Kaufman"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"}],"scopus_import":"1","_id":"742","intvolume":"       195","title":"On expansion and topological overlap","pubrep_id":"912","department":[{"_id":"UlWa"}],"date_created":"2018-12-11T11:48:16Z","article_processing_charge":"Yes (via OA deal)","publication_status":"published","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","related_material":{"record":[{"relation":"earlier_version","id":"1378","status":"public"}]},"file":[{"file_id":"5835","creator":"kschuh","relation":"main_file","access_level":"open_access","date_updated":"2020-07-14T12:47:58Z","content_type":"application/pdf","file_name":"s10711-017-0291-4.pdf","date_created":"2019-01-15T13:44:05Z","checksum":"d2f70fc132156504aa4c626aa378a7ab","file_size":412486}],"type":"journal_article","date_published":"2018-08-01T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"publist_id":"6925","oa":1,"language":[{"iso":"eng"}],"has_accepted_license":"1","publication":"Geometriae Dedicata","month":"08","project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"oa_version":"Published Version"},{"language":[{"iso":"eng"}],"conference":{"start_date":"2016-06-14","name":"SoCG: Symposium on Computational Geometry","location":"Medford, MA, USA","end_date":"2016-06-17"},"has_accepted_license":"1","month":"06","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"oa_version":"Published Version","related_material":{"record":[{"status":"public","id":"742","relation":"later_version"}]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"content_type":"application/pdf","file_name":"IST-2016-623-v1+1_LIPIcs-SoCG-2016-35.pdf","date_updated":"2020-07-14T12:44:47Z","checksum":"cee65b0e722d50f9d1cc70c90ec1d59b","file_size":536923,"date_created":"2018-12-12T10:08:38Z","creator":"system","file_id":"4699","relation":"main_file","access_level":"open_access"}],"type":"conference","date_published":"2016-06-01T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"publist_id":"5833","oa":1,"file_date_updated":"2020-07-14T12:44:47Z","quality_controlled":"1","page":"35.1 - 35.10","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing","author":[{"full_name":"Dotterrer, Dominic","first_name":"Dominic","last_name":"Dotterrer"},{"full_name":"Kaufman, Tali","last_name":"Kaufman","first_name":"Tali"},{"first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":1,"_id":"1378","intvolume":"        51","pubrep_id":"623","title":"On expansion and topological overlap","alternative_title":["LIPIcs"],"department":[{"_id":"UlWa"}],"date_created":"2018-12-11T11:51:41Z","publication_status":"published","ddc":["510"],"volume":51,"year":"2016","citation":{"mla":"Dotterrer, Dominic, et al. <i>On Expansion and Topological Overlap</i>. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">10.4230/LIPIcs.SoCG.2016.35</a>.","short":"D. Dotterrer, T. Kaufman, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10.","ista":"Dotterrer D, Kaufman T, Wagner U. 2016. On expansion and topological overlap. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 35.1-35.10.","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing; 2016:35.1-35.10. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">10.4230/LIPIcs.SoCG.2016.35</a>","apa":"Dotterrer, D., Kaufman, T., &#38; Wagner, U. (2016). On expansion and topological overlap (Vol. 51, p. 35.1-35.10). Presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">https://doi.org/10.4230/LIPIcs.SoCG.2016.35</a>","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA, 2016, vol. 51, p. 35.1-35.10.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap,” 51:35.1-35.10. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">https://doi.org/10.4230/LIPIcs.SoCG.2016.35</a>."},"date_updated":"2023-09-27T12:29:56Z","abstract":[{"lang":"eng","text":"We give a detailed and easily accessible proof of Gromov's Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map X → ℝd there exists a point p ∈ ℝd whose preimage intersects a positive fraction μ &gt; 0 of the d-cells of X. More generally, the conclusion holds if ℝd is replaced by any d-dimensional piecewise-linear (PL) manifold M, with a constant μ that depends only on d and on the expansion properties of X, but not on M."}],"day":"01","doi":"10.4230/LIPIcs.SoCG.2016.35"},{"_id":"1381","scopus_import":1,"author":[{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac","first_name":"Isaac","last_name":"Mabillard"},{"orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","department":[{"_id":"UlWa"}],"date_created":"2018-12-11T11:51:41Z","title":"Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range","alternative_title":["LIPIcs"],"pubrep_id":"621","intvolume":"        51","page":"51.1 - 51.12","quality_controlled":"1","file_date_updated":"2020-07-14T12:44:47Z","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH","date_updated":"2021-01-12T06:50:17Z","year":"2016","citation":{"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.","short":"I. Mabillard, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2016, p. 51.1-51.12.","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>.","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.","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>.","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>","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>"},"doi":"10.4230/LIPIcs.SoCG.2016.51","day":"01","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."}],"volume":51,"ddc":["510"],"has_accepted_license":"1","oa_version":"Published Version","project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"month":"06","language":[{"iso":"eng"}],"conference":{"start_date":"2016-06-14","name":"SoCG: Symposium on Computational Geometry","end_date":"2016-06-17","location":"Medford, MA, USA"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2016-06-01T00:00:00Z","type":"conference","oa":1,"publist_id":"5830","file":[{"file_id":"4791","creator":"system","relation":"main_file","access_level":"open_access","date_updated":"2020-07-14T12:44:47Z","file_name":"IST-2016-621-v1+1_LIPIcs-SoCG-2016-51.pdf","content_type":"application/pdf","date_created":"2018-12-12T10:10:06Z","checksum":"92c0c3735fe908f8ded6e484005cb3b1","file_size":622969}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public"},{"volume":212,"acknowledgement":"Supported by the ERC Adv anced Grant No. 267165. ","date_updated":"2023-02-23T10:34:31Z","citation":{"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.","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>.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Israel Journal of Mathematics 212 (2016) 37–79.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” <i>Israel Journal of Mathematics</i>, vol. 212, no. 1. Springer, pp. 37–79, 2016.","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>.","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>"},"year":"2016","doi":"10.1007/s11856-016-1294-9","day":"01","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."}],"page":"37 - 79","quality_controlled":"1","publisher":"Springer","_id":"1411","scopus_import":1,"author":[{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"full_name":"Sedgwick, Eric","last_name":"Sedgwick","first_name":"Eric"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","first_name":"Martin","full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"issue":"1","publication_status":"published","department":[{"_id":"UlWa"}],"date_created":"2018-12-11T11:51:52Z","title":"Untangling two systems of noncrossing curves","intvolume":"       212","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1302.6475"}],"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","id":"2244","relation":"earlier_version"}]},"date_published":"2016-05-01T00:00:00Z","type":"journal_article","publist_id":"5796","oa":1,"language":[{"iso":"eng"}],"publication":"Israel Journal of Mathematics","oa_version":"Preprint","project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"month":"05"},{"day":"01","doi":"10.1007/s00454-014-9584-7","abstract":[{"text":"A result of Boros and Füredi (d = 2) and of Bárány (arbitrary d) asserts that for every d there exists cd &gt; 0 such that for every n-point set P ⊂ ℝd, some point of ℝd is covered by at least (Formula presented.) of the d-simplices spanned by the points of P. The largest possible value of cd has been the subject of ongoing research. Recently Gromov improved the existing lower bounds considerably by introducing a new, topological proof method. We provide an exposition of the combinatorial component of Gromov's approach, in terms accessible to combinatorialists and discrete geometers, and we investigate the limits of his method. In particular, we give tighter bounds on the cofilling profiles for the (n - 1)-simplex. These bounds yield a minor improvement over Gromov's lower bounds on cd for large d, but they also show that the room for further improvement through the cofilling profiles alone is quite small. We also prove a slightly better lower bound for c3 by an approach using an additional structure besides the cofilling profiles. We formulate a combinatorial extremal problem whose solution might perhaps lead to a tight lower bound for cd.","lang":"eng"}],"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>.","short":"J. Matoušek, U. Wagner, Discrete &#38; Computational Geometry 52 (2014) 1–33.","ista":"Matoušek J, Wagner U. 2014. On Gromov’s method of selecting heavily covered points. Discrete &#38; Computational Geometry. 52(1), 1–33.","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>","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.","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>."},"year":"2014","date_updated":"2021-01-12T06:55:38Z","volume":52,"acknowledgement":"Swiss National Science Foundation (SNF 200021-125309, 200020-138230, 200020-12507)","date_created":"2018-12-11T11:56:01Z","department":[{"_id":"UlWa"}],"publication_status":"published","intvolume":"        52","title":"On Gromov's method of selecting heavily covered points","scopus_import":1,"_id":"2154","issue":"1","author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli"}],"publisher":"Springer","quality_controlled":"1","page":"1 - 33","publist_id":"4852","oa":1,"type":"journal_article","date_published":"2014-07-01T00:00:00Z","main_file_link":[{"url":"http://arxiv.org/abs/1102.3515","open_access":"1"}],"status":"public","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"oa_version":"Submitted Version","month":"07","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}]},{"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1302.6475"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"1411"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","date_published":"2013-09-01T00:00:00Z","oa":1,"publist_id":"4707","language":[{"iso":"eng"}],"conference":{"location":"Bordeaux, France","end_date":"2013-09-25","name":"GD: Graph Drawing and Network Visualization","start_date":"2013-09-23"},"project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","month":"09","volume":8242,"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.","citation":{"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. <i>Untangling Two Systems of Noncrossing Curves</i>. Vol. 8242, Springer, 2013, pp. 472–83, doi:<a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">10.1007/978-3-319-03841-4_41</a>.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">https://doi.org/10.1007/978-3-319-03841-4_41</a>.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. 2013;8242:472-483. doi:<a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">10.1007/978-3-319-03841-4_41</a>","apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2013). Untangling two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network Visualization, Bordeaux, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">https://doi.org/10.1007/978-3-319-03841-4_41</a>"},"year":"2013","date_updated":"2023-02-21T17:03:07Z","external_id":{"arxiv":["1302.6475"]},"day":"01","arxiv":1,"doi":"10.1007/978-3-319-03841-4_41","abstract":[{"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 &quot;untangle&quot; 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 (&quot;holes&quot;), 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. ","lang":"eng"}],"quality_controlled":"1","series_title":"Lecture Notes in Computer Science","page":"472 - 483","publisher":"Springer","scopus_import":1,"_id":"2244","author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"last_name":"Sedgwick","first_name":"Eric","full_name":"Sedgwick, Eric"},{"first_name":"Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"department":[{"_id":"UlWa"}],"date_created":"2018-12-11T11:56:32Z","publication_status":"published","intvolume":"      8242","title":"Untangling two systems of noncrossing curves","alternative_title":["LNCS"]}]