The straight-line RAC drawing problem is NP-hard

DOI10.1007/978-3-642-18381-2_6zbMATH Open1298.68198arXiv1009.5227OpenAlexW2110336351WikidataQ59702333 ScholiaQ59702333MaRDI QIDQ3075508FDOQ3075508

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

Publication date: 15 February 2011

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

Abstract: Recent cognitive experiments have shown that the negative impact of an edge crossing on the human understanding of a graph drawing, tends to be eliminated in the case where the crossing angles are greater than 70 degrees. This motivated the study of RAC drawings, in which every pair of crossing edges intersects at right angle. In this work, we demonstrate a class of graphs with unique RAC combinatorial embedding and we employ members of this class in order to show that it is NP-hard to decide whether a graph admits a straight-line RAC drawing.

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

Recommendations

• The straight-line RAC drawing problem is NP-hard
• On the perspectives opened by right angle crossing drawings
• On the perspectives opened by right angle crossing drawings
• Drawing Graphs with Right Angle Crossings
• Drawing graphs with right angle crossings

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) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Crossing Number is NP-Complete
• Title not available (Why is that?)
• Empirical evaluation of aesthetics-based graph layout
• Drawing graphs. Methods and models
• Drawing Graphs with Right Angle Crossings
• On the perspectives opened by right angle crossing drawings
• A characterization of complete bipartite RAC graphs
• Area, curve complexity, and crossing resolution of non-planar graph drawings
• Maximizing the total resolution of graphs
• The quality ratio of RAC drawings and planar drawings of planar graphs
• On the Angular Resolution of Planar Graphs
• A Note on Rectilinearity and Angular Resolution
• Drawing Graphs in the Plane with High Resolution
• The straight-line RAC drawing problem is NP-hard

Cited In (17)

• Large angle crossing drawings of planar graphs in subquadratic area
• 2-layer right angle crossing drawings
• Circular right-angle crossing drawings in linear time
• Drawing graphs with right angle crossings
• Graph Drawing via Gradient Descent, $$(GD)^2$$
• RAC-Drawability is ∃ℝ-complete and Related Results
• Vertex angle and crossing angle resolution of leveled tree drawings
• RAC-drawability is \(\exists \mathbb{R} \)-complete
• Graphs with large total angular resolution
• Title not available (Why is that?)
• Graphs with large total angular resolution
• Right angle crossing graphs and 1-planarity
• Right angle crossing graphs and 1-planarity
• RAC drawings in subcubic area
• The straight-line RAC drawing problem is NP-hard
• Fixed edge-length graph drawing is NP-hard
• Stress-Plus-X (SPX) graph layout

This page was built for publication: The straight-line RAC drawing problem is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3075508)