Graph Drawing in the Cloud: Privately Visualizing Relational Data Using Small Working Storage

Goodrich, Michael T. and Ohrimenko, Olga and Tamassia, Roberto (2013) Graph Drawing in the Cloud: Privately Visualizing Relational Data Using Small Working Storage. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 43-54 (Official URL:

Full text not available from this repository.


We study graph drawing in a cloud-computing context where data is stored externally and processed using a small local working storage. We show that a number of classic graph drawing algorithms can be efficiently implemented in such a framework where the client can maintain privacy while constructing a drawing of her graph.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_5
Classifications:J Applications > J.001 General
S Software and Systems > S.120 Visualization
ID Code:1296

Repository Staff Only: item control page


Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and issues in data stream systems. In: Proc. Symp. on Principles of Database Systems, pp. 1–16 (2002)

Barghouti, N., Mocenigo, J., Lee, W.: Grappa: A GRAPh PAckage in Java. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 336–343. Springer, Heidelberg (1997)

Bertolazzi, P., Cohen, R.F., Di Battista, G., Tamassia, R., Tollis, I.G.: How to draw a series-parallel digraph. Internat. J. Comput. Geom. Appl. 4, 385–402 (1994)

Binucci, C., Brandes, U., Di Battista, G., Didimo, W., Gaertler, M., Palladino, P., Patrignani, M., Symvonis, A., Zweig, K.: Drawing Trees in a Streaming Model. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 292–303. Springer, Heidelberg (2010)

Bridgeman, S., Garg, A., Tamassia, R.: A graph drawing and translation service on the World Wide Web. Int. J. Comp. Geom. Appl. 9(4-5), 419–446 (1999)

Cohen, R.F., Di Battista, G., Tamassia, R., Tollis, I.G.: Dynamic graph drawings: Trees, series-parallel digraphs, and planar ST-digraphs. SIAM J. Comput. 24(5), 970–1001 (1995)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999)

Di Battista, G., Tamassia, R., Tollis, I.G.: Area requirement and symmetry display of planar upward drawings. Discrete Comput. Geom. 7(4), 381–401 (1992)

Eppstein, D., Goodrich, M.T., Tamassia, R.: Privacy-preserving data-oblivious geometric algorithms for geographic data. In: 18th ACM Adv. in Geographic Information Systems, ACM GIS, pp. 13–22 (2010),

Feldman, J., Muthukrishnan, S., Sidiropoulos, A., Stein, C., Svitkina, Z.: On distributing symmetric streaming computations. ACM Trans. Algorithms 6(4), 66:1–66:19 (2010),

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Goldreich, O.: Foundations of Cryptography, vol. II. Cambridge University Press (2004)

Goodrich, M.T.: Randomized Shellsort: A simple oblivious sorting algorithm. In: Symposium on Discrete Algorithms, SODA, pp. 1–16 (2010)

Goodrich, M.T., Mitzenmacher, M.: Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 576–587. Springer, Heidelberg (2011)

Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious RAM simulation with efficient worst-case access overhead. In: Proc. ACM Workshop on Cloud Computing Security, CCSW, pp. 95–100 (2011)

Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Practical oblivious storage. In: Proc. ACM Conference on Data and Application Security and Privacy, CODASPY (2012)

Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious RAM simulation. In: Proc. ACM-SIAM Symp. on Discrete Algorithms, SODA (2012)

Goodrich, M.T., Ohrimenko, O., Tamassia, R.: Data-oblivious graph drawing model and algorithms. CoRR abs/1209.0756 (2012)

Henzinger, M.R., Raghavan, P., Rajagopalan, S.: Computing on data streams. In: External Memory Algorithms. Discrete Mathematics and Theoretical Computer Science, vol. 50, pp. 107–118. AMS (1999)

Johnson, B., Shneiderman, B.: Tree-maps: A space-filling approach to the visualization of hierarchical information structures. In: IEEE Visualization, pp. 284–291 (1991)

Muthukrishnan, S.: Data Streams: Algorithms and Applications. In: Foundations and Trends in Theoretical Computer Science, vol. 1. Now Publishers (2005)

Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. Journal of Computer and System Sciences 26(3), 362–381 (1983)

Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1(4), 321–341 (1986)