Untangling Two Systems of Noncrossing Curves

摘要

We consider two systems (α_1,...,α_m) and (β_1, ...,β_n) of 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 α_i by a self-homeomorphism of M; more precisely, we seek an homeomorphism Φ: M→M fixing the boundary of M 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 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.