Crossing Numbers of Beyond-Planar Graphs.
2019
We study the 1-planar, quasi-planar, and fan-planar crossing number in comparison to the (unrestricted) crossing number of graphs. We prove that there are n-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has \(\varOmega (n)\) crossings, while \(\mathcal {O}(1)\) crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
27
References
3
Citations
NaN
KQI