The Approximate Rectangle of Influence Drawability Problem

We prove that all planar graphs have an open/closed $(ε_1 ,ε_2)$-rectangle of influence drawing for $ε_1 > 0$ and $ε_2 > 0$, while there are planar graphs which do not admit an open/closed $(ε1,0)$-rectangle of influence drawing and planar graphs which do not admit a $(0,ε_2)$-rectangle of influence drawing. We then show that all outerplanar graphs have an open/closed $(0,ε_2)$-rectangle of influence drawing for any ε_2 ≥ 0. We also prove that if $ε_2 > 2$ an open/closed $(0, ε_2)$-rectangle of influence drawing of an outerplanar graph can be computed in polynomial area. For values of $ε_2$ such that $ε_2 ≤ 2$, we describe a drawing algorithm that computes $(0,ε_2)$-rectangle of influence drawings of binary trees in area $O(n^{2 + f(\varepsilon _2)})$, where $f(ε_2)$ is a logarithmic function that tends to infinity as $ε_2$ tends to zero, and n is the number of vertices of the input tree