Untangling two systems of noncrossing curves Conference Paper

Author(s): Matoušek, Jiří; Sedgwick, Eric; Tancer, Martin; Wagner, Uli
Title: Untangling two systems of noncrossing curves
Title Series: LNCS
Affiliation IST Austria
Abstract: 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.
Keywords: Curves on 2-manifolds; Lickorish's theorem; Simultaneous planar drawings
Conference Title: GD: Graph Drawing and Network Visualization
Volume: 8242
Conference Dates: September 23-25, 2013
Conference Location: Bordeaux, France
ISBN: 978-331927260-3
Publisher: Springer  
Date Published: 2013-09-01
Start Page: 472
End Page: 483
DOI: 10.1007/978-3-319-03841-4_41
Notes: 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.
Open access: yes (repository)
IST Austria Authors
  1. Uli Wagner
    50 Wagner
Related IST Austria Work