\(\mathsf{NIC}\)-planar graphs
From MaRDI portal
Publication:2410219
DOI10.1016/j.dam.2017.08.015zbMath1372.05047arXiv1701.04375OpenAlexW2964235359MaRDI QIDQ2410219
Josef Reislhuber, Franz-Josef Brandenburg, Kathrin Hanauer, Daniel Neuwirth, Christian Bachmaier
Publication date: 17 October 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1701.04375
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Density (toughness, etc.) (05C42)
Related Items
Map graphs having witnesses of large girth ⋮ On fan-crossing and fan-crossing free graphs ⋮ Recognizing IC-Planar and NIC-Planar Graphs ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ An annotated bibliography on 1-planarity ⋮ Unnamed Item ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A heuristic approach towards drawings of graphs with high crossing resolution ⋮ Characterizing and recognizing 4-map graphs ⋮ On \((p, 1)\)-total labelling of NIC-planar graphs ⋮ Characterizing 5-map graphs by 2-fan-crossing graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ Compact drawings of 1-planar graphs with right-angle crossings and few bends ⋮ On RAC drawings of graphs with one bend per edge ⋮ Remarks on the joins of 1-planar graphs ⋮ The maximal 1-planarity and crossing numbers of graphs ⋮ Linear arboricity of NIC-planar graphs ⋮ Quantitative Restrictions on Crossing Patterns ⋮ Edge Partitions and Visibility Representations of 1-planar Graphs ⋮ Right Angle Crossing Drawings of Graphs ⋮ IC-Planar Graphs Are 6-Choosable
Cites Work
- Unnamed Item
- Outer 1-planar graphs
- Recognizing and drawing IC-planar graphs
- Drawing complete multipartite graphs on the plane with restrictions on crossings
- A linear-time algorithm for testing outer-1-planarity
- Drawing graphs with right angle crossings
- On the maximum number of edges in quasi-planar graphs
- Optimal 1-planar graphs which triangulate other surfaces
- Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
- Every planar map is four colorable. I: Discharging
- The structure of plane graphs with independent crossings and its applications to coloring problems
- Right angle crossing graphs and 1-planarity
- Ein Sechsfarbenproblem auf der Kugel
- Algorithms for graphs embeddable with few crossings per edge
- Recognizing hole-free 4-map graphs in cubic time
- Parameterized Complexity of 1-Planarity
- Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
- Re-embeddings of Maximum 1-Planar Graphs
- Coloring plane graphs with independent crossings
- Map graphs
- Über 1-optimale Graphen
- Edge-Disjoint Spanning Trees of Finite Graphs
- Chromatic number, independence ratio, and crossing number
- Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
- Arboricity and Subgraph Listing Algorithms
- Zur Struktur 1‐planarer Graphen
- Geometric Thickness of Complete Graphs
- On the Density of Maximal 1-Planar Graphs
- 1-Planarity of Graphs with a Rotation System
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- Enumeration of simple complete topological graphs