Testing gap \(k\)-planarity is NP-complete
From MaRDI portal
Publication:2032139
DOI10.1016/j.ipl.2020.106083OpenAlexW3126317692MaRDI QIDQ2032139
John C. Urschel, Jake L. Wellens
Publication date: 16 June 2021
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.02104
Related Items (4)
Recognizing and embedding simple optimal 2-planar graphs ⋮ Crossing Numbers of Beyond-Planar Graphs Revisited ⋮ Weak-dynamic coloring of graphs beyond-planarity ⋮ $$\textit{\textbf{k}}$$-Planar Graphs
Cites Work
- Improving the crossing lemma by finding more crossings in sparse graphs
- Algorithms for drawing graphs: An annotated bibliography
- Note on \(k\)-planar crossing numbers
- On the \(k\)-planar local crossing number
- Gap-planar graphs
- Empirical evaluation of aesthetics-based graph layout
- On RAC drawings of 1-planar graphs
- An annotated bibliography on 1-planarity
- Algorithms for graphs embeddable with few crossings per edge
- On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
- Crossing Number is NP-Complete
- On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
- Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
- New lower bound techniques for VLSI
- Crossing-Free Subgraphs
- Crossing Numbers of Graphs
- Parameterized Complexity of 1-Planarity
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- TRÉMAUX TREES AND PLANARITY
- Crossing numbers of beyond-planar graphs
This page was built for publication: Testing gap \(k\)-planarity is NP-complete
