Untangling two systems of noncrossing curves

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Untangling two systems of noncrossing curves

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Untangling two systems of noncrossing curves

Popis výsledku anglicky

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

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Kreslení grafů a jejich geometrické reprezentace</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 21st International Symposium on Graph Drawing GD'13

ISBN

978-3-319-03840-7

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

472-483

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Bordeaux, Francie

Datum konání akce

23. 9. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—