The straight-line RAC drawing problem is NP-hard

DOI10.1007/978-3-642-18381-2_6MaRDI QIDQ3075508zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• A Note on Rectilinearity and Angular Resolution
• A characterization of complete bipartite RAC graphs
• Area, curve complexity, and crossing resolution of non-planar graph drawings
• Crossing Number is NP-Complete
• Drawing Graphs in the Plane with High Resolution
• Drawing Graphs with Right Angle Crossings
• Drawing graphs. Methods and models
• Empirical evaluation of aesthetics-based graph layout
• Maximizing the total resolution of graphs
• On the Angular Resolution of Planar Graphs
• On the perspectives opened by right angle crossing drawings
• The quality ratio of RAC drawings and planar drawings of planar graphs
• 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$$
• Vertex angle and crossing angle resolution of leveled tree drawings
• RAC-Drawability is ∃ℝ-complete and Related Results
• RAC-drawability is \(\exists \mathbb{R} \)-complete
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• Graphs with large total angular resolution
• 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)