The Approximate Rectangle of Influence Drawability ProblemDi Giacomo, Emilio and Liotta, Giuseppe and Meijer, Henk (2013) The Approximate Rectangle of Influence Drawability Problem. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 114125(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractWe 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.
Actions (login required)
