On RAC drawings of 1-planar graphs

DOI10.1016/j.tcs.2017.05.039zbMath1372.68202arXiv1608.08418OpenAlexW2624658792WikidataQ59702334 ScholiaQ59702334MaRDI QIDQ2402260

Michael A. Bekos, Walter Didimo, Giuseppe Liotta, Saeed Mehrabi, Fabrizio Montecchiani

Publication date: 7 September 2017

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

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

zbMATH Keywords

NP-hardness1-planarityRAC drawings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (22)

RAC-drawability is \(\exists \mathbb{R} \)-complete ⋮ On fan-crossing and fan-crossing free graphs ⋮ The Stub Resolution of 1-planar Graphs ⋮ An annotated bibliography on 1-planarity ⋮ An annotated review on graph drawing and its applications ⋮ Unnamed Item ⋮ RAC-Drawability is ∃ℝ-complete and Related Results ⋮ Gap-Planar Graphs ⋮ Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles ⋮ A heuristic approach towards drawings of graphs with high crossing resolution ⋮ Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles ⋮ Embedding-preserving rectangle visibility representations of nonplanar graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ Compact drawings of 1-planar graphs with right-angle crossings and few bends ⋮ Gap-planar graphs ⋮ Ortho-polygon visibility representations of embedded graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ Testing gap \(k\)-planarity is NP-complete ⋮ RAC drawings in subcubic area ⋮ Fan-Planar Graphs ⋮ Right Angle Crossing Drawings of Graphs ⋮ 1-planarity testing and embedding: an experimental study

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing and drawing IC-planar graphs
• A note on 1-planar graphs
• Graphs that admit right angle crossing drawings
• 2-layer right angle crossing drawings
• Drawing complete multipartite graphs on the plane with restrictions on crossings
• Drawing graphs with right angle crossings
• Planar graphs: Theory and algorithms
• Graphs drawn with few crossings per edge
• Empirical evaluation of aesthetics-based graph layout
• Density of straight-line 1-planar graph drawings
• Right angle crossing graphs and 1-planarity
• Area requirement of graph drawings with few crossings per edge
• Ein Sechsfarbenproblem auf der Kugel
• An annotated bibliography on 1-planarity
• Algorithms for graphs embeddable with few crossings per edge
• Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends
• The Crossing-Angle Resolution in Graph Drawing
• Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
• Heuristics for the Maximum 2-layer RAC Subgraph Problem
• Fáry’s Theorem for 1-Planar Graphs
• 1-Visibility Representations of 1-Planar Graphs
• On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
• Re-embeddings of Maximum 1-Planar Graphs
• Maximizing the Total Resolution of Graphs
• Topology-Driven Force-Directed Algorithms
• The Straight-Line RAC Drawing Problem is NP-Hard
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Rectilinear drawings of graphs
• On-Line Planarity Testing
• EVERY OUTER-1-PLANE GRAPH HAS A RIGHT ANGLE CROSSING DRAWING
• On the Perspectives Opened by Right Angle Crossing Drawings

This page was built for publication: On RAC drawings of 1-planar graphs