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, Redmond, WA, USA , pp. 114-125 (Official URL:

Full text not available from this repository.


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
ID Code:1302

Repository Staff Only: item control page


Alamdari, S., Biedl, T.: Planar Open Rectangle-of-Influence Drawings with Non-aligned Frames. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 14–25. Springer, Heidelberg (2012)

Angelini, P., Bruckdorfer, T., Chiesa, M., Frati, F., Kaufmann, M., Squarcella, C.: On the Area Requirements of Euclidean Minimum Spanning Trees. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 25–36. Springer, Heidelberg (2011)

Bachmaier, C., Brandenburg, F.J., Forster, M.: Track planarity testing and embedding. In: Proc. of SOFSEM 2004, vol. 2, pp. 3–17. MatFyzPress (2004)

de Berg, M.T., Carlsson, S., Overmars, M.H.: A general approach to dominance in the plane. J. Algorithms 13, 274–296 (1992)

Biedl, T., Bretscher, A., Meijer, H.: Rectangle of Influence Drawings of Graphs without Filled 3-Cycles. In: Kratochvíl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 359–368. Springer, Heidelberg (1999)

Bose, P., Lenhart, W., Liotta, G.: Characterizing proximity trees. Algorithmica 16, 83–110 (1996)

Di Battista, G., Liotta, G., Whitesides, S.: The strength of weak proximity. J. Discrete Algorithms 4(3), 384–400 (2006)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H.: Drawing a tree as a minimum spanning tree approximation. J. Comput. Syst. Sci. 78(2), 491–503 (2012)

Evans, W., Gansner, E.R., Kaufmann, M., Liotta, G., Meijer, H., Spillner, A.: Approximate Proximity Drawings. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 166–178. Springer, Heidelberg (2011)

Frati, F., Kaufmann, M.: Polynomial area bounds for MST embeddings of trees. Comput. Geom. Theory and Applications 44(9), 529–543 (2011)

Ichino, M., Sklansky, J.: The relative neighborhood graph for mixed feature variables. Pattern Recognition 18(2), 161–167 (1985)

Liotta, G.: Proximity drawings. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (to appear)

Liotta, G., Lubiw, A., Meijer, H., Whitesides, S.: The rectangle of influence drawability problem. Comput. Geom. Theory and Applications 10(1), 1–22 (1998)

Miura, K., Matsuno, T., Nishizeki, T.: Open rectangle-of-influence drawings of inner triangulated plane graphs. Discrete & Computational Geometry 41(4), 643–670 (2009)

Miura, K., Nishizeki, T.: Rectangle-of-influence drawings of four-connected plane graphs. In: APVIS 2005. CRPIT, vol. 45, pp. 75–80. Australian Computer Society (2005)

Miura, K., Nakano, S.-I., Nishizeki, T.: Convex Grid Drawings of Four-Connected Plane Graphs. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol. 1969, pp. 254–265. Springer, Heidelberg (2000)

Overmars, M.H., Wood, D.: On rectangular visibility. J. Algorithms 9, 372–390 (1988)

Sadasivam, S., Zhang, H.: Closed rectangle-of-influence drawings for irreducible triangulations. Comput. Geom. Theory and Applications 44(1), 9–19 (2011)

Zhang, H., Vaidya, M.: On open rectangle-of-influence and rectangular dual drawings of plane graphs. Discrete Mathematics, Algorithms and Applications 1(3), 319–333 (2009)