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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

153 Downloads (Pure)


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.
Originele taal-2Engels
Aantal pagina's23
StatusGepubliceerd - 2017

Bibliografische nota

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


Duik in de onderzoeksthema's van 'Gap-planar graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit