The Straight-Line RAC Drawing Problem Is NP-Hard

DOI10.1007/978-3-642-18381-2_6zbMath1298.68198arXiv1009.5227OpenAlexW2110336351WikidataQ59702333 ScholiaQ59702333MaRDI QIDQ3075508

Antonios Symvonis, Michael A. Bekos, Evmorfia N. Argyriou

Publication date: 15 February 2011

Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (12)

Circular right-angle crossing drawings in linear time ⋮ Right Angle Crossing Graphs and 1-Planarity ⋮ Right angle crossing graphs and 1-planarity ⋮ Stress-Plus-X (SPX) graph layout ⋮ Vertex angle and crossing angle resolution of leveled tree drawings ⋮ 2-layer right angle crossing drawings ⋮ Large Angle Crossing Drawings of Planar Graphs in Subquadratic Area ⋮ Drawing graphs with right angle crossings ⋮ Graphs with large total angular resolution ⋮ Graphs with large total angular resolution ⋮ RAC drawings in subcubic area ⋮ Graph Drawing via Gradient Descent, $$(GD)^2$$

Cites Work

• Unnamed Item
• A characterization of complete bipartite RAC graphs
• Empirical evaluation of aesthetics-based graph layout
• Maximizing the Total Resolution of Graphs
• The Quality Ratio of RAC Drawings and Planar Drawings of Planar Graphs
• Drawing Graphs in the Plane with High Resolution
• The Straight-Line RAC Drawing Problem is NP-Hard
• Drawing Graphs with Right Angle Crossings
• Crossing Number is NP-Complete
• Area, Curve Complexity, and Crossing Resolution of Non-planar Graph Drawings
• On the Angular Resolution of Planar Graphs
• A Note on Rectilinearity and Angular Resolution
• On the Perspectives Opened by Right Angle Crossing Drawings
• Drawing graphs. Methods and models

This page was built for publication: The Straight-Line RAC Drawing Problem Is NP-Hard