--- res: bibo_abstract: - 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.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Jiří foaf_name: Matoušek, Jiří foaf_surname: Matoušek - foaf_Person: foaf_givenName: Eric foaf_name: Sedgwick, Eric foaf_surname: Sedgwick - foaf_Person: foaf_givenName: Martin foaf_name: Tancer, Martin foaf_surname: Tancer foaf_workInfoHomepage: http://www.librecat.org/personId=38AC689C-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-1191-6714 - foaf_Person: foaf_givenName: Uli foaf_name: Wagner, Uli foaf_surname: Wagner foaf_workInfoHomepage: http://www.librecat.org/personId=36690CA2-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-1494-0568 bibo_doi: 10.1007/s11856-016-1294-9 bibo_issue: '1' bibo_volume: 212 dct_date: 2016^xs_gYear dct_language: eng dct_publisher: Springer@ dct_title: Untangling two systems of noncrossing curves@ ...