论文标题
带有圆形弧和右角横梁的绘图图
Drawing Graphs with Circular Arcs and Right-Angle Crossings
论文作者
论文摘要
在图形的RAC图中，顶点由平面中的点表示，相邻的顶点通过线段连接，交叉必须形成直角。接受此类图纸的图形是RAC图。 RAC图是超越平面图的，并且已经进行了广泛的研究。特别是，众所周知，具有N顶点的RAC图最多具有4N-10个边缘。 我们介绍了RAC图的超类，我们称之为ARC-RAC图。图形是ARC-RAC，如果它允许在边缘用圆形弧表示的图形和交叉形成正确角度的图形。我们提供了Turán类型的结果，表明具有N顶点的ARC-RAC图最多具有14n-12个边缘，并且有4.5n-O（n）边缘的N-Vertex ARC-RAC图。
In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that admit such drawings are RAC graphs. RAC graphs are beyond-planar graphs and have been studied extensively. In particular, it is known that a RAC graph with n vertices has at most 4n - 10 edges. We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with n vertices has at most 14n - 12 edges and that there are n-vertex arc-RAC graphs with 4.5n - o(n) edges.
