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%2F16%3A10328975" target="_blank" >RIV/00216208:11320/16:10328975 - isvavai.cz</a>

Výsledek na webu

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

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

Název v anglickém jazyce

Untangling two systems of noncrossing curves

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

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í

2016

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 periodika

Israel Journal of Mathematics

ISSN

0021-2172

e-ISSN

—

Svazek periodika

212

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

IL - Stát Izrael

Počet stran výsledku

43

Strana od-do

37-79

Kód UT WoS článku

000377265600002

EID výsledku v databázi Scopus

2-s2.0-84971014023