Untangling two systems of noncrossing curves Journal Article


Author(s): Matoušek, Jiří; Sedgwick, Eric; Tancer, Martin; Wagner, Uli
Article Title: Untangling two systems of noncrossing curves
Affiliation IST Austria
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.
Journal Title: Israel Journal of Mathematics
Volume: 212
Issue 1
ISSN: 0021-2172
Publisher: Springer  
Date Published: 2016-05-01
Start Page: 37
End Page: 79
URL:
DOI: 10.1007/s11856-016-1294-9
Notes: Supported by the ERC Adv anced Grant No. 267165. ∗∗ Partially supported by Grant GRADR Eurogiga GIG/11/E023. † Supported by a Goran Gustafsson postdoctoral fellowship. †† Supported by the Swiss National Science Foundation (Grant SNSF-PP00P2- 138948). Received June 12, 2013 and in revised form March 7, 2014 37 We would like to thank the authors of [GHR13] for making a draft of their paper available to us, and, in particular, T. Huynh for an e-mail correspondence. We also thank an anonymous referee for many valuable comments and in particular for a suggestion of using local orientations in the proof of Proposition 5.2 which replaced our original (longer) homology-based proof.
Open access: yes (repository)
IST Austria Authors
  1. Uli Wagner
    43 Wagner
  2. Martin Tancer
    8 Tancer
Related IST Austria Work