Gap-Planar Graphs.

Bae, Sang Won and Baffier, Jean-Francois and Chun, Jinhee and Eades, Peter and Eickmeyer, Kord and Grilli, Luca and Hong, Seok-Hee and Korman, Matias and Montecchiani, Fabrizio and Rutter, Ignaz and Tóth, Csaba D. (2017) Gap-Planar Graphs. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 531-545(Official URL:

Full text not available from this repository.


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 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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings

Actions (login required)

View Item View Item