---
_id: '1411'
abstract:
- lang: eng
text: We consider two systems (α1, …, αm) and (β1, …,βn) of simple 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 ai by a self-homeomorphism of
M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise
such that the total number of crossings of the ai 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. The proofs rely, among other things, on a result concerning simultaneous
planar drawings of graphs by Erten and Kobourov.
acknowledgement: 'Supported by the ERC Adv anced Grant No. 267165. '
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Eric
full_name: Sedgwick, Eric
last_name: Sedgwick
- first_name: Martin
full_name: Tancer, Martin
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing
curves. Israel Journal of Mathematics. 2016;212(1):37-79. doi:10.1007/s11856-016-1294-9
apa: Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2016). Untangling
two systems of noncrossing curves. Israel Journal of Mathematics. Springer.
https://doi.org/10.1007/s11856-016-1294-9
chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling
Two Systems of Noncrossing Curves.” Israel Journal of Mathematics. Springer,
2016. https://doi.org/10.1007/s11856-016-1294-9.
ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems
of noncrossing curves,” Israel Journal of Mathematics, vol. 212, no. 1.
Springer, pp. 37–79, 2016.
ista: Matoušek J, Sedgwick E, Tancer M, Wagner U. 2016. Untangling two systems of
noncrossing curves. Israel Journal of Mathematics. 212(1), 37–79.
mla: Matoušek, Jiří, et al. “Untangling Two Systems of Noncrossing Curves.” Israel
Journal of Mathematics, vol. 212, no. 1, Springer, 2016, pp. 37–79, doi:10.1007/s11856-016-1294-9.
short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Israel Journal of Mathematics
212 (2016) 37–79.
date_created: 2018-12-11T11:51:52Z
date_published: 2016-05-01T00:00:00Z
date_updated: 2023-02-23T10:34:31Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s11856-016-1294-9
intvolume: ' 212'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1302.6475
month: '05'
oa: 1
oa_version: Preprint
page: 37 - 79
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
grant_number: PP00P2_138948
name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication: Israel Journal of Mathematics
publication_status: published
publisher: Springer
publist_id: '5796'
quality_controlled: '1'
related_material:
record:
- id: '2244'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Untangling two systems of noncrossing curves
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 212
year: '2016'
...