The Approximate Rectangle of Influence Drawability Problem.

Let ε, ε be two non negative numbers. An approximate rectangle of influence drawing (also called ( ε, ε)-RID) is a proximity drawing of a graph such that: (i) if u, v are adjacent vertices then their rectangle of influence 'scaled down' by the factor $\frac{1}{1+\varepsilon_{1}}$ does not contain other vertices of the drawing; (ii) if u, v are not adjacent, then their rectangle of influence 'blown-up' by the factor 1+ ε contains some vertices of the drawing other than u and v. Firstly, we prove that all planar graphs have an ( ε, ε)-RID for any ε>0 and ε>0, while there exist planar graphs which do not admit an ( ε,0)-RID and planar graphs which do not admit a (0, ε)-RID. Then, we investigate (0, ε)-RIDs; we prove that both the outerplanar graphs and a suitably defined family of graphs without separating 3-cycles admit this type of drawing. Finally, we study polynomial area approximate rectangle of influence drawings and prove that (0, ε)-RIDs of proper track planar graphs (a superclass of the outerplanar graphs) can be computed in polynomial area for any ε>2. As for values of ε such that ε≤2, we describe a drawing algorithm that computes (0, ε)-RIDs of binary trees in area $O(n^{c + f(\varepsilon_{2})})$, where c is a positive constant, f( ε) is a poly-logarithmic function that tends to infinity as ε tends to zero, and n is the number of vertices of the input tree. [ABSTRACT FROM AUTHOR]