Grid drawings of graphs with constant edge-vertex resolution

We study the algorithmic problem of computing drawings of graphs in which (i) each vertex is a disk with fixed radius ρ, (ii) each edge is a straight-line segment connecting the centers of the two disks representing its end-vertices, (iii) no two disks intersect, and (iv) the distance between an edge segment and the center of a non-incident disk, called edge-vertex resolution, is at least ρ. We call such drawings disk-link drawings. In this paper we focus on the case of constant edge-vertex resolution, namely [Fromula Presented] (i.e., disks of unit diameter). We prove that star graphs, which trivially admit straight-line drawings in linear area, require quadratic area in any such disk-link drawing. On the positive side, we present constructive techniques that yield improved upper bounds for the area requirements of disk-link drawings for several (planar and nonplanar) graph classes, including bounded bandwidth, complete, and planar graphs. In particular, the presented bounds for complete and planar graphs are asymptotically tight.