The Approximate Rectangle of Influence Drawability Problem

Di Giacomo, Emilio and Liotta, Giuseppe and Meijer, Henk (2013) The Approximate Rectangle of Influence Drawability Problem. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 114-125(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_11
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.999 Others
P Styles > P.720 Straight-line
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 21 Nov 2013 13:40
Last Modified: 21 Nov 2013 13:40
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1302

Actions (login required)

View Item View Item