Crossing numbers of beyond-planar graphs (Q5918404)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 7437222
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Crossing numbers of beyond-planar graphs |
scientific article; zbMATH DE number 7437222 |
Statements
Crossing numbers of beyond-planar graphs (English)
0 references
1 December 2021
0 references
The article is devoted to further study the question of the best planar realization of a graph, including the one with the minimum possible number of edge intersections. Particular attention is paid to the study of three families of graphs, namely, \(k\)-planar, fan-planar and \(k\)-quasi-planar graphs. The authors prove ``that there are \(n\)-vertex 1-planar (quasi-planar, fan-planar) graphs such that any \(1\)-planar (quasi-planar, fan-planar) drawing has \(\Omega(n)\) crossings, while \(\mathcal{O}(1)\) crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.''
0 references
crossing numbers
0 references
beyond planarity
0 references
1-planar graph
0 references
0.8500375151634216
0 references
0.8471279144287109
0 references
0.8451489806175232
0 references
0.8436617851257324
0 references
0.8270997405052185
0 references
