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 twodimensional 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 selfhomeomorphism 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 3manifolds. 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:

00212172

Publisher:

Springer

Date Published:

20160501

Start Page: 
37

End Page:

79

URL: 

DOI: 
10.1007/s1185601612949

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 SNSFPP00P2 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 email 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) homologybased proof.

Open access: 
yes (repository) 