Drawing planar graphs with circular arcs
Drawing planar graphs with circular arcs
复制标题
用圆弧绘制平面图
DOI：
10.1007/3-540-46648-7_12
复制
发表时间：
1999
影响因子：
0.8
通讯作者：
S. Kobourov
中科院分区：
文献类型：
--
作者：
C. C. Cheng;C. A. Duncan;M. Goodrich;S. Kobourov
本文讨论了在保持良好的角度分辨率和较小的绘图面积的情况下绘制圆弧平面图的问题。我们给出了仅使用一条圆弧绘制边的图形区域的下界。我们还给出了一个绘制n点平面图的算法，使得边是两个连续圆弧的序列。该算法运行Ino(N)时间，在保持θ(1/d(V))角分辨率的同时，将图嵌入到Theo(N)×O(N)网格上，其中v是顶点v的度数。由于在这种情况下，我们使用无限半径的圆弧，这也是第一个同时获得良好的角度分辨率、小面积和使用直线段每条边最多一个折弯的算法。最后，我们展示了如何创建边是光滑的C_1连续曲线的图形，该曲线由至多三个圆弧的序列表示。
In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular arc. We also give an algorithm for drawingn-vertex planar graphs such that the edges are sequences of two continuous circular arcs. The algorithm runs inO(n) time and embeds the graph on theO(n) ×O(n) grid, while maintaining θ(1/d(v)) angular resolution, whered(v) is the degree of vertexv. Since in this case we use circular arcs of infinite radius, this is also the first algorithm to simultaneously achieve good angular resolution, small area and at most one bend per edge using straight-line segments. Finally, we show how to create drawings in which edges are smoothC1-continuous curves, represented by a sequence of at most three circular arcs.