9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details

Untangling two systems of noncrossing curves

Presented by Martin TANCER
Type: Oral presentation
Track: Discrete and Computational Geometry


We consider two systems of curves $(\alpha_1,\ldots,\alpha_m)$ and $(\beta_1,\ldots,\beta_n)$ drawn on $M$, which is a compact two-dimensional orientable surface of genus $g\ge 0$ and with $h\ge 1$ 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 $\varphi\colon M\toM$ fixing the boundary of $M$ pointwise such that the total number of crossings of the $\alpha_i$ with the $\varphi(\beta_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., $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.


Location: Koper, Slovenia

Primary authors