All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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