Gap-Planar Graphs

DOI10.1007/978-3-319-73915-1_41MaRDI QIDQ4625141zbMATH OpenOpenAlexFDO

Authors Sang Won Bae, Jean-François Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Fabrizio Montecchiani, Ignaz Rutter, Matias Korman, Csaba D. Tóth

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.07653

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We introduce the family of $k$-gap-planar graphs for $kgeq0$, 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.

Recommendations

• Gap-planar graphs
• scientific article; zbMATH DE number 4154462
• scientific article; zbMATH DE number 1099607
• scientific article; zbMATH DE number 475620
• scientific article; zbMATH DE number 4189751
• PLANAR GRAPHS AND RELATED TOPICS
• Planar Digraphs
• GAPS BETWEEN CONNECTED FINITE GRAPHS
• Connectivity of planar graphs

Cites work

• scientific article; zbMATH DE number 3604926 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 1-planarity of graphs with a rotation system
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• A linear-time algorithm for testing outer-1-planarity
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Algorithms for graphs embeddable with few crossings per edge
• An annotated bibliography on 1-planarity
• Circular right-angle crossing drawings in linear time
• Edges and switches, tunnels and bridges
• Fan-planarity: properties and complexity
• Gap-Planar Graphs
• Graphs drawn with few crossings per edge
• Improving the crossing lemma by finding more crossings in sparse graphs
• Minimizing maximum indegree
• On a problem of P. Turan concerning graphs
• On the Size of Planarly Connected Crossing Graphs
• On the density of non-simple 3-planar graphs
• On the maximum number of edges in quasi-planar graphs
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• Outer 1-planar graphs
• Progress on partial edge drawings
• Quasi-planar graphs have a linear number of edges
• Testing Full Outer-2-planarity in Linear Time
• The crossing number of K5,n
• The density of fan-planar graphs
• The number of edges in k-quasi-planar graphs
• Two-Planar Graphs Are Quasiplanar

Cited in

(10)

• Min-\(k\)-planar drawings of graphs
• Testing gap \(k\)-planarity is NP-complete
• Min-k-planar drawings of graphs
• Gap-Planar Graphs
• Gap-planar graphs
• On RAC drawings of graphs with one bend per edge
• Quantitative restrictions on crossing patterns
• Crossing numbers of beyond planar graphs re-revisited: a framework approach
• Parameterized algorithms for beyond-planar crossing numbers
• Flow-Cut Gaps and Face Covers in Planar Graphs

This page was built for publication: Gap-Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625141)