Gap-planar graphs

Sang Won Bae, Jean Francois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, Csaba D. Tóth

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers
EditorsF. Frati, K-L. Ma
Place of PublicationBerlin
Number of pages15
ISBN (Electronic)978-3-319-73915-1
ISBN (Print)9783319739144
Publication statusPublished - 1 Jan 2018
Event25th International Symposium on Graph Drawing and Network Visualization (GD 2017) - Boston, United States
Duration: 25 Sept 201727 Sept 2017
Conference number: 25

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
Abbreviated titleGD 2017
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'Gap-planar graphs'. Together they form a unique fingerprint.

Cite this