On the Maximum Number of Crossings in Star-Simple Drawings of Kn with No Empty Lens
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On the Maximum Number of Crossings in Star-Simple Drawings of Kn with No Empty Lens
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
On the Maximum Number of Crossings in Star-Simple Drawings of Kn with No Empty Lens
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>SC</sub> - Článek v periodiku v databázi SCOPUS
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA21-32817S" target="_blank" >GA21-32817S: Algoritmické, strukturální a složitostní aspekty geometrických konfigurací</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2022
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ů
Údaje specifické pro druh výsledku
Název periodika
Journal of Graph Algorithms and Applications
ISSN
1526-1719
e-ISSN
—
Svazek periodika
26
Číslo periodika v rámci svazku
3
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
19
Strana od-do
381-399
Kód UT WoS článku
—
EID výsledku v databázi Scopus
2-s2.0-85135736811