2022/04/29 by Michael A. Bekos, Martin Gronemann, Bekos, Michael A. +5
Computer Science · Environmental Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Remote Sensing and LiDAR Applications
paper · pdf · doi:10.48550/arxiv.2204.14040
openalex publication_date 2022/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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=minn-3,f. Our result improves the previously best-known area bound of (3n-7)x(3n-7)/2 by Chrobak, Goodrich and Tamassia.