Gap-planar Graphs
Bae, Sang Won, Baffier, Jean-Francois, Chun, Jinhee, Eades, Peter, Eickmeyer, Kord, Grilli, Luca, Hong, Seok-Hee, Korman, Matias, Montecchiani, Fabrizio, Rutter, Ignaz, T\'oth, Csaba D. · arXiv (Cornell University) · 2017
We introduce the family of $k$-gap-planar graphs for $k \geq 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 finds motivation in edge casing, as a $k$-gap-planar graph can be drawn crossing-free after introducing at most $k$ local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs.