---
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@
...