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

doi:10.1007/978-3-319-73915-1_41

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 proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers
Editors	F. Frati, K-L. Ma
Place of Publication	Berlin
Publisher	Springer
Pages	531-545
Number of pages	15
ISBN (Electronic)	978-3-319-73915-1
ISBN (Print)	9783319739144
DOIs	https://doi.org/10.1007/978-3-319-73915-1_41
Publication status	Published - 1 Jan 2018
Event	25th International Symposium on Graph Drawing and Network Visualization (GD 2017) - Boston, United States Duration: 25 Sept 2017 → 27 Sept 2017 Conference number: 25 https://gd2017.ccis.northeastern.edu/

Publication series

Name	Lecture Notes in Computer Science
Volume	10692
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
Abbreviated title	GD 2017
Country/Territory	United States
City	Boston
Period	25/09/17 → 27/09/17
Internet address	https://gd2017.ccis.northeastern.edu/

Access to Document

10.1007/978-3-319-73915-1_41

Cite this

Bae, S. W., Baffier, J. F., Chun, J., Eades, P., Eickmeyer, K., Grilli, L., Hong, S. H., Korman, M., Montecchiani, F., Rutter, I., & Tóth, C. D. (2018). Gap-planar graphs. In F. Frati, & K-L. Ma (Eds.), Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers (pp. 531-545). (Lecture Notes in Computer Science ; Vol. 10692). Springer. https://doi.org/10.1007/978-3-319-73915-1_41

@inproceedings{1b4278dea7224404a422ab9ed850aa48,

title = "Gap-planar graphs",

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

author = "Bae, {Sang Won} and Baffier, {Jean Francois} and Jinhee Chun and Peter Eades and Kord Eickmeyer and Luca Grilli and Hong, {Seok Hee} and Matias Korman and Fabrizio Montecchiani and Ignaz Rutter and T{\'o}th, {Csaba D.}",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-73915-1_41",

language = "English",

isbn = "9783319739144",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "531--545",

editor = "F. Frati and K-L. Ma",

booktitle = "Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers",

address = "Germany",

note = "25th International Symposium on Graph Drawing and Network Visualization (GD 2017), GD 2017 ; Conference date: 25-09-2017 Through 27-09-2017",

url = "https://gd2017.ccis.northeastern.edu/",

}

Bae, SW, Baffier, JF, Chun, J, Eades, P, Eickmeyer, K, Grilli, L, Hong, SH, Korman, M, Montecchiani, F, Rutter, I & Tóth, CD 2018, Gap-planar graphs. in F Frati & K-L Ma (eds), Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. Lecture Notes in Computer Science , vol. 10692, Springer, Berlin, pp. 531-545, 25th International Symposium on Graph Drawing and Network Visualization (GD 2017), Boston, Massachusetts, United States, 25/09/17. https://doi.org/10.1007/978-3-319-73915-1_41

Gap-planar graphs. / Bae, Sang Won; Baffier, Jean Francois; Chun, Jinhee et al.
Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. ed. / F. Frati; K-L. Ma. Berlin: Springer, 2018. p. 531-545 (Lecture Notes in Computer Science ; Vol. 10692).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Gap-planar graphs

AU - Bae, Sang Won

AU - Baffier, Jean Francois

AU - Chun, Jinhee

AU - Eades, Peter

AU - Eickmeyer, Kord

AU - Grilli, Luca

AU - Hong, Seok Hee

AU - Korman, Matias

AU - Montecchiani, Fabrizio

AU - Rutter, Ignaz

AU - Tóth, Csaba D.

N1 - Conference code: 25

PY - 2018/1/1

Y1 - 2018/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85041799045&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-73915-1_41

DO - 10.1007/978-3-319-73915-1_41

M3 - Conference contribution

AN - SCOPUS:85041799045

SN - 9783319739144

T3 - Lecture Notes in Computer Science

SP - 531

EP - 545

BT - Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers

A2 - Frati, F.

A2 - Ma, K-L.

PB - Springer

CY - Berlin

T2 - 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

Y2 - 25 September 2017 through 27 September 2017

ER -

Gap-planar graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this