Untangling two systems of noncrossing curves
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10328975" target="_blank" >RIV/00216208:11320/16:10328975 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s11856-016-1294-9" target="_blank" >http://dx.doi.org/10.1007/s11856-016-1294-9</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s11856-016-1294-9" target="_blank" >10.1007/s11856-016-1294-9</a>
Alternative languages
Result language
angličtina
Original language name
Untangling two systems of noncrossing curves
Original language description
We consider two systems (alpha(1), ... ,alpha(m)) and (beta(1), ... , beta(n)) of simple curves drawn on a compact two-dimensional surface M with boundary. 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 a, 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 a, 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 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Graph Drawings and Representations</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Israel Journal of Mathematics
ISSN
0021-2172
e-ISSN
—
Volume of the periodical
212
Issue of the periodical within the volume
1
Country of publishing house
IL - THE STATE OF ISRAEL
Number of pages
43
Pages from-to
37-79
UT code for WoS article
000377265600002
EID of the result in the Scopus database
2-s2.0-84971014023