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.
翻译:我们继续研究三层相连接平面图的直线网格图区域要求,过去几十年对此进行了深入调查。受图编辑等应用程序的推动,我们还要求获得的图纸具有边缘-垂直分辨率,即脊椎与任何非偏向边缘之间的最近距离,受一个不取决于图的大小的常数所限制。我们提出了一个绘图算法,将一个带有正脊椎和内面的三层相连接的平面图作为输入,并在一个大小整格(n-2+ax(n-2+a),即a=min{n-3,f})上用边缘-垂直分辨率至少为1.5的平面图直线图进行计算。我们的结果改进了Chrobak、Goodrich和Tamassia先前最著名的区域(3n-7x(3n-7)/2)的界限,即Chrobak、Goodrich和Tamasia。