Gap-planar graphs.

Abstract We introduce the family of k-gap-planar graphs for k ≥ 0 , i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition is motivated by applications in edge casing, as a k -gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k -gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k -gap-planar complete graphs, and the computational complexity of recognizing k -gap-planar graphs. [ABSTRACT FROM AUTHOR]