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