Earlier Version

Untangling two systems of noncrossing curves

J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483.

Conference Paper | Published | English

Scopus indexed
Matoušek, Jiří; Sedgwick, Eric; Tancer, MartinIST Austria ; Wagner, UliIST Austria
Series Title
We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a compact two-dimensional 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 self-homeomorphism 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 3-manifolds. 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.
Publishing Year
Date Published
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 e-mail correspondence.
472 - 483
GD: Graph Drawing and Network Visualization
Conference Location
Bordeaux, France
Conference Date
2013-09-23 – 2013-09-25

Cite this

Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. 2013;8242:472-483. doi:10.1007/978-3-319-03841-4_41
Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2013). Untangling two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network Visualization, Bordeaux, France: Springer. https://doi.org/10.1007/978-3-319-03841-4_41
Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-319-03841-4_41.
J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.
Matoušek J, Sedgwick E, Tancer M, Wagner U. 2013. Untangling two systems of noncrossing curves. 8242, 472–483.
Matoušek, Jiří, et al. Untangling Two Systems of Noncrossing Curves. Vol. 8242, Springer, 2013, pp. 472–83, doi:10.1007/978-3-319-03841-4_41.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Later Version


Marked Publications

Open Data IST Research Explorer


arXiv 1302.6475

Search this title in

Google Scholar