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