The Approximate Rectangle of Influence Drawability Problem

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