\(\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