On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens
| Autor: | Stefan Felsner, Michael Hoffmann, Kristin Knorr, Jan Kynčl, Irene Parada |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | Journal of Graph Algorithms and Applications, 26 (3) |
| ISSN: | 1526-1719 |
| DOI: | 10.7155/jgaa.00600 |
| Popis: | 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. Journal of Graph Algorithms and Applications, 26 (3) ISSN:1526-1719 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|