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.1016/j.tcs.2018.05.029

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

INF - System Information Sciences

Research output: Contribution to journal › Article › peer-review

20 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 is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-planar graphs.

Original language	English
Pages (from-to)	36-52
Number of pages	17
Journal	Theoretical Computer Science
Volume	745
DOIs	https://doi.org/10.1016/j.tcs.2018.05.029
Publication status	Published - 2018 Oct 12

Keywords

Beyond planarity k-gap-planar graphs
Complete graphs
Density results
Recognition problem
k-planar graphs
k-quasiplanar graphs

Access to Document

10.1016/j.tcs.2018.05.029

Cite this

@article{648a0bccb803475cb30b94463ed3fc30,

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 is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-planar graphs.",

keywords = "Beyond planarity k-gap-planar graphs, Complete graphs, Density results, Recognition problem, k-planar graphs, k-quasiplanar 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.}",

note = "Funding Information: Partially supported by the NSF awards CCF-1422311 and CCF-1423615. Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = oct,

day = "12",

doi = "10.1016/j.tcs.2018.05.029",

language = "English",

volume = "745",

pages = "36--52",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

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.

PY - 2018/10/12

Y1 - 2018/10/12

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 is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-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 is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-planar graphs.

KW - Beyond planarity k-gap-planar graphs

KW - Complete graphs

KW - Density results

KW - Recognition problem

KW - k-planar graphs

KW - k-quasiplanar graphs

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

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

U2 - 10.1016/j.tcs.2018.05.029

DO - 10.1016/j.tcs.2018.05.029

M3 - Article

AN - SCOPUS:85048165888

SN - 0304-3975

VL - 745

SP - 36

EP - 52

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Gap-planar graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this