--- _id: '1411' 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. acknowledgement: 'Supported by the ERC Adv anced Grant No. 267165. ' author: - first_name: Jiří full_name: Matoušek, Jiří last_name: Matoušek - first_name: Eric full_name: Sedgwick, Eric last_name: Sedgwick - first_name: Martin full_name: Tancer, Martin id: 38AC689C-F248-11E8-B48F-1D18A9856A87 last_name: Tancer orcid: 0000-0002-1191-6714 - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 citation: ama: Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. Israel Journal of Mathematics. 2016;212(1):37-79. doi:10.1007/s11856-016-1294-9 apa: Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2016). Untangling two systems of noncrossing curves. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-016-1294-9 chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” Israel Journal of Mathematics. Springer, 2016. https://doi.org/10.1007/s11856-016-1294-9. ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” Israel Journal of Mathematics, vol. 212, no. 1. Springer, pp. 37–79, 2016. 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.” Israel Journal of Mathematics, vol. 212, no. 1, Springer, 2016, pp. 37–79, doi:10.1007/s11856-016-1294-9. short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Israel Journal of Mathematics 212 (2016) 37–79. date_created: 2018-12-11T11:51:52Z date_published: 2016-05-01T00:00:00Z date_updated: 2023-02-23T10:34:31Z day: '01' department: - _id: UlWa doi: 10.1007/s11856-016-1294-9 intvolume: ' 212' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1302.6475 month: '05' oa: 1 oa_version: Preprint page: 37 - 79 project: - _id: 25FA3206-B435-11E9-9278-68D0E5697425 grant_number: PP00P2_138948 name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics' publication: Israel Journal of Mathematics publication_status: published publisher: Springer publist_id: '5796' quality_controlled: '1' related_material: record: - id: '2244' relation: earlier_version status: public scopus_import: 1 status: public title: Untangling two systems of noncrossing curves type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 212 year: '2016' ...