Crossing Numbers of Beyond-Planar Graphs

Markus Chimani; Philipp Kindermann; Fabrizio Montecchiani; Pavel Valtr

paper

Crossing Numbers of Beyond-Planar Graphs

arXiv:1908.03153

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.

Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)