论文标题
具有恒定边缘vertex分辨率的平面图的凸网格图
Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution
论文作者
论文摘要
我们继续研究3个连接平面图的凸直线网格图的面积需求，该图在过去几十年中已经进行了深入研究。在应用程序（例如图形编辑器）的动机中，我们还要求获得的图纸具有有界的边缘 - vertex分辨率，即，顶点和任何非固定边缘之间的最接近的距离是由不取决于图的大小的常数降低的。我们提出了一种图形算法，该算法将带有N顶点和F内部面的3个连接的平面图作为输入，并在整数大小（n-2+a）x（n-2+a）上计算具有边缘 - vertex分辨率至少1/2的凸直线图，其中a = min = min = n-3，f}。我们的结果改善了Chrobak，Goodrich和Tamassia的（3N-7）X（3N-7）/2的界面。
We continue the study of the area requirement of convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motivated by applications, such as graph editors, we additionally require the obtained drawings to have bounded edge-vertex resolution, that is, the closest distance between a vertex and any non-incident edge is lower bounded by a constant that does not depend on the size of the graph. We present a drawing algorithm that takes as input a 3-connected plane graph with n vertices and f internal faces and computes a convex straight-line drawing with edge-vertex resolution at least 1/2 on an integer grid of size (n-2+a)x(n-2+a), where a=min{n-3,f}. Our result improves the previously best-known area bound of (3n-7)x(3n-7)/2 by Chrobak, Goodrich and Tamassia.
