论文标题
小皮带区域的RAC绘图
RAC Drawings in Subcubic Area
论文作者
论文摘要
在本文中，我们研究了曲线复杂性与直角交叉图（RAC图）之间的权衡，这在图形图中是一个具有挑战性的理论问题。给定具有$ n $顶点和$ m $边缘的图表，我们提供了一种带有曲线复杂性$ 6 $的RAC图算法和面积$ O（n^{2.75}）$，它需要时间$ o（n+m）$。我们的算法在RAC图纸的区域上改善了先前的上限$ O（n^3）$。
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.
