We study the algorithmic problem of computing drawings of graphs in which (i) each vertex is a disk with constant radius r , (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 edge-vertex resolution is at least r, that is, no edge segment intersects a non-adjacent disk . We call such drawings disk-link drawings. This model is motivated by the fact that common graph editors represent vertices as geometric features (usually either as disks or as squares) of fixed size. In this scenario, vertex-vertex and edge-vertex overlaps cause visual clutter and may generate ambiguities. Since such issues can be solved by scaling up the drawingby a suitable factor , we present constructive techniques that yield more compact upper bounds for the area requirements of disk-link drawings for several (planar and nonplanar) graph classes, including proper level, bounded bandwidth, complete, planar and outerplanar graphs .
We study the algorithmic problem of computing drawings of graphs in which (i) each vertex is a disk with fixed radius \rho , (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, callededge-vertex resolution, is at least \rho . We call such drawings disk-link drawings. In this paper we focus on the case of constant edge-vertex resolution, namely \rho=\frac{1 , 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 .
R
constant radius r
fixed radius \rho
R
edge-vertex resolution is at least r, that is, no edge segment intersects a non-adjacent disk
distance between an edge segment and the center of a non-incident disk, called
A
edge-vertex resolution
A
, is at least \rho
R
disk-link drawings. This model is motivated by the fact that common graph editors represent vertices as geometric features (usually either as disks or as squares) of fixed size. In this scenario, vertex-vertex and
disk-link drawings
A
. In this paper we focus on the case of constant
R
overlaps cause visual clutter and may generate ambiguities. Since such issues can be solved by scaling up the drawingby a suitable factor
resolution, namely \rho=\frac{1
R
more compact
improved
D
proper level,
R
planar and outerplanar graphs
and planar graphs. In particular, the presented bounds for complete and planar graphs are asymptotically tight