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 twodimensional 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 selfhomeomorphism 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 3manifolds. 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 2manifolds; Lickorish's theorem; Simultaneous planar drawings

Conference Title:

GD: Graph Drawing and Network Visualization

Volume: 
8242

Conference Dates:

September 2325, 2013

Conference Location:

Bordeaux, France

ISBN:

9783319272603

Publisher:

Springer

Date Published:

20130901

Start Page: 
472

End Page:

483

URL: 

DOI: 
10.1007/9783319038414_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 email correspondence.

Open access: 
yes (repository) 