RAC Drawings in Subcubic Area

2020/01/09 by Rahmati, Zahed, Emami, Fatemeh
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2001.02867

Abstract

In this paper, we study tradeoffs between curve complexity and area of Right Angle Crossing drawings (RAC drawings), which is a challenging theoretical problem in graph drawing. Given a graph with n vertices and m edges, we provide a RAC drawing algorithm with curve complexity 6 and area O(n^2.75), which takes time O(n+m). Our algorithm improves the previous upper bound O(n³), by Di Giacomo et al., on the area of RAC drawings.

Related

• Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs
• RAC-drawability is ∃ℝ-complete
• Axis-Parallel Right Angle Crossing Graphs
• RAC Drawings of Graphs with Low Degree
• Outer-(ap)RAC Graphs