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 Ω(n) crossings, while O(1) crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.
Crossing numbers of beyond-planar graphs
Montecchiani F.;
2021
Abstract
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 Ω(n) crossings, while O(1) crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
