Martin Tancer: Untangling two systems of noncrossing curves

joint work with Jiri Matousek, Eric Sedgwick and Uli Wagner

We consider two systems of curves (\alpha_1,...,\alpha_m) and
(\beta_1,...,\beta_n) drawn on M, which is a compact two-dimensional
orientable surface of genus g >= 0 and with h > 0 holes. Each \alpha_i and
each \beta_j is either an arc meeting the boundary of M at its two
endpoints, or a closed curve. The \alpha_i are pairwise disjoint except
for possibly sharing endpoints, and similarly for the \beta_j. We want to
``untangle'' the \beta_j from the \alpha_i by a self-homeomorphism of M;
more precisely, we seek a homeomorphism \phi:M->M fixing the boundary of M
pointwise such that the total number of crossings of the \alpha_i with the
\phi(\beta_j) is as small as possible. This problem is motivated by an
application in the algorithmic theory of embeddings and 3-manifolds.

We sketch a proof that if M is planar, i.e., g=0, then O(mn) crossings
can be achieved (independently of h), which is asymptotically tight, as
an easy lower bound shows. For M of arbitrary genus, we obtain an
O((m+n)^4) upper bound, again independent of h and g. The proofs rely,
among others, on a result concerning simultaneous planar drawings of
graphs by Erten and Kobourov.

If time permits, we will also discuss an extension to the non-orientable
case. This yields to further application to graph minor testing which is
a recent result of Geelen, Huynh and Richter.