Gap-planar graphs

S.W. Bae, J.F. Baffier, J. Chun, P. Eades, K. Eickmeyer, L. Grilli, S.-H. Hong, M. Korman, F. Montecchiani, I. Rutter, C.D. Tóth

Research output: Contribution to journalArticleAcademic

179 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number1708.07653
Number of pages23
JournalarXiv
Publication statusPublished - 2017

Bibliographical note

Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

Keywords

  • cs.CG

Fingerprint

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

Cite this