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%2F13%3A10173455" target="_blank" >RIV/00216208:11320/13:10173455 - isvavai.cz</a>
Result on the web
<a href="http://link.springer.com/chapter/10.1007%2F978-3-319-03841-4_41" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-319-03841-4_41</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-03841-4" target="_blank" >10.1007/978-3-319-03841-4</a>
Alternative languages
Result language
angličtina
Original language name
Untangling two systems of noncrossing curves
Original language description
We consider two systems (? 1,...,? m ) and (? 1,...,? n ) of 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 pairwisedisjoint except for possibly sharing endpoints, and similarly for the ? j . We want to "untangle" the ? j from the ? i by a self-homeomorphism of M ; more precisely, we seek an homeomorphism ?MRIGHTWARDS ARROWM fixing the boundary of M 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 M is planar, i.e., a sphere with h GREATER-THAN OREQUAL TO 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
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
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
2013
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
Article name in the collection
Proceedings of the 21st International Symposium on Graph Drawing GD'13
ISBN
978-3-319-03840-7
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
472-483
Publisher name
Springer
Place of publication
Berlin
Event location
Bordeaux, Francie
Event date
Sep 23, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—