The Straight-Line RAC Drawing Problem is NP-Hard

DOI10.7155/jgaa.00274zbMath1254.05120OpenAlexW1990163141MaRDI QIDQ3143754

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

Publication date: 4 December 2012

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00274

zbMATH Keywords

polyline drawing

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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (24)

RAC-drawability is \(\exists \mathbb{R} \)-complete ⋮ On RAC drawings of 1-planar graphs ⋮ The Stub Resolution of 1-planar Graphs ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ Combinatorial properties and recognition of unit square visibility graphs ⋮ Unnamed Item ⋮ L-visibility drawings of IC-planar graphs ⋮ RAC-Drawability is ∃ℝ-complete and Related Results ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ 1-fan-bundle-planar drawings of graphs ⋮ A heuristic approach towards drawings of graphs with high crossing resolution ⋮ A greedy heuristic for crossing-angle maximization ⋮ A linear-time algorithm for testing full outer-2-planarity ⋮ Unnamed Item ⋮ On RAC drawings of graphs with one bend per edge ⋮ On RAC drawings of graphs with one bend per edge ⋮ The Straight-Line RAC Drawing Problem Is NP-Hard ⋮ Unnamed Item ⋮ Testing Full Outer-2-planarity in Linear Time ⋮ Beyond Planar Graphs: Introduction ⋮ Right Angle Crossing Drawings of Graphs ⋮ Angular Resolutions: Around Vertices and Crossings ⋮ On the Number of Edges of Fan-Crossing Free Graphs

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