Gap-planar graphs

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.

Authors

• Sang Won Bae
• Jean-Francois Baffier
• Jinhee Chun
• Peter Eades
• Kord Eickmeyer
• Luca Grilli
• Seok-Hee Hong
• Matias Korman
• Fabrizio Montecchiani Università degli Studi di Perugia
• Ignaz Rutter University of Passau
• Csaba D. Tóth

Keywords

• Beyond planarity k-gap-planar graphs
• Density results
• Complete graphs
• Recognition problem
• k-planar graphs
• k-quasiplanar graphs