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

7 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/

Funding

Research started at the NII Shonan Meeting “Algorithmics for Beyond Planar Graphs.” The authors thank the organizers, and Yota Otachi for useful discussions. Bae was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2015R1D1A1A01057220). Baffier was supported by JST-ERATO Grant Number JPMJER1201, Japan. Eades and Hong were partially supported by ARC DP160104148. Korman was partially supported by MEXT KAKENHI No. 15H02665, 17K12635 and JST ERATO Grant Number JPMJER1305. Tóth was supported in part by the NSF awards CCF-1422311 and CCF-1423615.

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

Funding

Access to Document

Other files and links

Fingerprint

Cite this