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”

On the Maximum Number of Crossings in Star-Simple Drawings of Kn with No Empty Lens

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455552" target="_blank" >RIV/00216208:11320/22:10455552 - isvavai.cz</a>

  • Result on the web

    <a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=7F--0H6sQC" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=7F--0H6sQC</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.7155/jgaa.00600" target="_blank" >10.7155/jgaa.00600</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    On the Maximum Number of Crossings in Star-Simple Drawings of Kn with No Empty Lens

  • Original language description

    A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. We forbid empty lenses, i.e., every lens is required to enclose a vertex, and show that with this restriction 3 · (n − 4)! is an upper bound on the number of crossings between two edges of a star-simple drawing of Kn. It follows that n! bounds the total number of crossings in the drawing. This is the first finite upper bound on the number of crossings in star-simple drawings of the complete graph Kn with no empty lens. For a lower bound we construct a star-simple drawing of Kn with no empty lens in which a pair of edges contributes 5^{n/2−2} crossings.

  • Czech name

  • Czech description

Classification

  • Type

    J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • Project

    <a href="/en/project/GA21-32817S" target="_blank" >GA21-32817S: Algorithmic, structural and complexity aspects of geometric configurations</a><br>

  • Continuities

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

Others

  • Publication year

    2022

  • 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

    Journal of Graph Algorithms and Applications

  • ISSN

    1526-1719

  • e-ISSN

  • Volume of the periodical

    26

  • Issue of the periodical within the volume

    3

  • Country of publishing house

    US - UNITED STATES

  • Number of pages

    19

  • Pages from-to

    381-399

  • UT code for WoS article

  • EID of the result in the Scopus database

    2-s2.0-85135736811