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)

Abstract

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
PublisherSpringer
Pages531-545
Number of pages15
ISBN (Electronic)978-3-319-73915-1
ISBN (Print)9783319739144
DOIs
Publication statusPublished - 1 Jan 2018
Event25th International Symposium on Graph Drawing and Network Visualization (GD 2017) - Boston, United States
Duration: 25 Sep 201727 Sep 2017
Conference number: 25
https://gd2017.ccis.northeastern.edu/

Publication series

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

Conference

Conference25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
Abbreviated titleGD 2017
CountryUnited States
CityBoston
Period25/09/1727/09/17
Internet address

Fingerprint

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

Cite this