RAC Drawings in Subcubic Area
share
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^3), by Di Giacomo et al., on the area of RAC drawings.
READ FULL TEXT