Gap-planar graphs

DOI10.1016/j.tcs.2018.05.029zbMath1400.68151OpenAlexW2749514451MaRDI QIDQ1786592

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

Publication date: 24 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.05.029

zbMATH Keywords

complete graphsrecognition problem\(k\)-quasiplanar graphsdensity results\(k\)-planar graphsbeyond planarity \(k\)-gap-planar graphs

Mathematics Subject Classification ID

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

Related Items (19)

Simplifying Non-Simple Fan-Planar Drawings ⋮ Tree densities in sparse graph classes ⋮ Simplifying non-simple fan-planar drawings ⋮ Crossing Numbers of Beyond-Planar Graphs Revisited ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Efficient generation of different topological representations of graphs beyond-planarity ⋮ Unnamed Item ⋮ Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar ⋮ On RAC drawings of graphs with one bend per edge ⋮ Testing gap \(k\)-planarity is NP-complete ⋮ Beyond Planar Graphs: Introduction ⋮ Quasi-planar Graphs ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ Fan-Planar Graphs ⋮ Crossing Layout in Non-planar Graph Drawings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Outer 1-planar graphs
• Recognizing and drawing IC-planar graphs
• Circular right-angle crossing drawings in linear time
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• A linear-time algorithm for testing outer-1-planarity
• Improving the crossing lemma by finding more crossings in sparse graphs
• On the maximum number of edges in quasi-planar graphs
• Edges and switches, tunnels and bridges
• Graphs drawn with few crossings per edge
• Quasi-planar graphs have a linear number of edges
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• Minimizing maximum indegree
• Fan-planarity: properties and complexity
• On RAC drawings of 1-planar graphs
• An annotated bibliography on 1-planarity
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• Algorithms for graphs embeddable with few crossings per edge
• Testing Full Outer-2-planarity in Linear Time
• The Crossing-Angle Resolution in Graph Drawing
• On the Number of Edges of Fan-Crossing Free Graphs
• On the Size of Planarly Connected Crossing Graphs
• On the Density of Non-simple 3-Planar Graphs
• Crossing Number is NP-Complete
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Guest Editors' Foreword and Overview
• Gap-Planar Graphs
• Two-Planar Graphs Are Quasiplanar
• 1-Planarity of Graphs with a Rotation System
• The Number of Edges in $k$-Quasi-planar Graphs
• Structure of Graphs with Locally Restricted Crossings
• Progress on Partial Edge Drawings
• The crossing number of K5,n
• On a problem of P. Turan concerning graphs

This page was built for publication: Gap-planar graphs