Roberto Tamassia's research currently focuses on information security, and in particular, authentication methods and protocols. He has developed an extensive suite of efficient cryptographic techniques for the authentication of data and streams in a distributed environment. These techniques allow the certification of query results on complex data structures, including graph-based and geometric search structures, and support full historical persistence and auditability. In addition to studying authentication from a cryptographic perspective, Roberto has implemented prototypes of distributed authentication systems for web services and email. Several patents on inventions arising from this work are pending and a commercialization effort for this work under the auspices of Brown University, in collaboration with IAM Technology, Inc., is in progress. Roberto's research on information security also includes work on access control, key distribution, privacy-preserving biometrics, forensic analysis, and trust negotiation. Roberto has made numerous contributions to the general area of analysis and design of algorithms, and especially to the fields of computational geometry, graph algorithms and graph drawing. Roberto has pioneered the field of graph drawing, which studies methods for the visualization of trees, graphs, and networks in two and three dimensions. In particular, his landmark papers on planar graph drawing algorithms are heavily cited and have given momentum to the field, which has its own annual conference since 1993. Roberto has also developed efficient techniques for the dynamization of fundamental graph and geometric data structures. Roberto has also done research on computer science education. He has developed new approaches to the teaching data structures and algorithms, which have contributed to the popularity of his series of textbooks, and he has developed tools for algorithm visualization and for the management of homework and programming assignments. His library of data structures and algorithms in Java (JDSL), developed primarily for educational purposes, has more than 10,000 users. Research interests include:

information security
cryptography
design and analysis of algorithms
graph drawing
computational geometry
computer science education

Selected Publications

Goodrich, M. T., and Tamassia, R. Data Structures and Algorithms in Java, fourth ed. Wiley, Aug 2005.

Tamassia, R., and Triandopoulos, N. Computational Bounds on Hierarchical Data Processing with Applications to Information Security. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP) (2005), Springer-Verlag, pp. 153-165. [ pdf ]

Goodrich, M. T., and Tamassia, R. Data Structures and Algorithms in Java, third ed. Wiley, 2004.

Tamassia, R., and Liotta, G. Graph Drawing. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, Eds. CRC Press, 2004.

Tamassia, R., Yao, D., and Winsborough, W. H. Role-Based Cascaded Delegation. In Proceedings of ACM Symposium on Access Control Models and Technologies (SACMAT) (2004), pp. 146-155. [ pdf ]

Goodrich, M. T., Tamassia, R., and Mount, D. Data Structures and Algorithms in C++. Wiley, Feb 2003.

Tamassia, R. Authenticated Data Structures. In Proceedings of the European Symposium on Algorithms (2003), Springer-Verlag, pp. 2-5. [ pdf ]

Bridgeman, S., and Tamassia, R. A User Study in Similarity Measures for Graph Drawing. Journal of Graph Algorithms and Applications 6, 3 (2002), 225-254. [ pdf ]

Chan, T., Goodrich, M. T., Kosaraju, S. R., and Tamassia, R. Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings. Computational Geometry: Theory and Applications 23, 2 (2002), 153-162. [ pdf ]

Goodrich, M. T., and Tamassia, R. Algorithm Design: Foundations, Analysis and Internet Examples. Wiley, New York, NY, 2002.

Di Battista, G., Tamassia, R., and Vismara, L. Incremental Convex Planarity Testing. Information and Computation 166 (2001), 1-33. [ pdf ]

Garg, A., and Tamassia, R. On the Computational Complexity of Upward and Rectilinear Planarity Testing. SIAM Journal Computing 31, 2 (2001), 601-625. [ pdf ]

Goodrich, M. T., and Tamassia, R. Data Structures and Algorithms in Java, second ed. Wiley, New York, NY, 2001.

Tamassia, R., and Vismara, L. A Case Study in Algorithm Engineering for Geometric Computing. International Journal of Computational Geometry and Applications 11, 1 (2001), 15-70. [ pdf ]

Tamassia, R., Goodrich, M. T., Vismara, L., Handy, M., Shubina, G., Cohen, R., Hudson, B., Baker, R. S., Gelfand, N., and Brandes, U. JDSL: The Data Structures Library in Java. Dr. Dobb's Journal 323 (Apr 2001).

Bridgeman, S. S., and Tamassia, R. Difference Metrics for Interactive Orthogonal Drawing Algorithms. Journal of Graph Algorithms and Applications 4, 3 (2000), 47-74. [ pdf ]

Bridgeman, S. S., Di Battista, G., Didimo, W., Liotta, G., Tamassia, R., and Vismara, L. Turn-Regularity and Optimal Area Drawings of Orthogonal Representations. Computational Geometry: Theory and Applications 16, 1 (2000), 53-93. [ pdf ]

Di Battista, G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., and Vismara, L. Drawing Directed Acyclic Graphs: An Experimental Study. International Journal of Computational Geometry and Applications 10, 6 (2000), 623-648. [ pdf ]

Tamassia, R. Graph Drawing. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000, pp. 937-971.

Tamassia, R., Tollis, I. G., and Vitter, J. S. A Parallel Algorithm for Planar Orthogonal Grid Drawings. Parallel Processing Letters 10, 1 (Mar 2000), 141-150. [ pdf ]

Vismara, L., Di Battista, G., Garg, A., Liotta, G., Tamassia, R., and Vargiu, F. Experimental Studies on Graph Drawing Algorithms. Software Practice and Experience 30 (2000), 1235-1284. [ pdf ]

Baker, J. E., Cruz, I. F., Liotta, G., and Tamassia, R. Visualizing Geometric Algorithms over the Web. Computational Geometry: Theory and Applications 12, 1-2 (1999), 125-152. [ pdf ]

Barequet, G., Bridgeman, S. S., Duncan, C. A., Goodrich, M. T., and Tamassia, R. Geometric Computing Over the Internet. IEEE Internet Computing 3, 2 (1999), 21-29. [ pdf ]

Bridgeman, S., Garg, A., and Tamassia, R. A Graph Drawing and Translation Service on the World Wide Web. International Journal of Computational Geometry and Applications 9, 4-5 (1999), 419-446.

Di Battista, G., Eades, P., Tamassia, R., and Tollis, I. G. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999. [ pdf ]

Di Battista, G., Tamassia, R., and Vismara, L. Output-Sensitive Reporting of Disjoint Paths. Algorithmica 23, 4 (1999), 302-340. [ pdf ]

Tamassia, R. Advances in the Theory and Practice of Graph Drawing. Theoretical Computer Science 217, 2 (1999), 235-254. [ pdf ]

Tamassia, R. Graph Drawing and Information Visualization. In Proceedings of the VIII Meetings on Computational Geometry (EGC8) (1999).

Bertolazzi, P., Di Battista, G., Mannino, C., and Tamassia, R. Optimal Upward Planarity Testing of Single-Source Digraphs. SIAM Journal on Computing 27, 1 (1998), 132-169. [ pdf ]

Devillers, O., Liotta, G., Preparata, F., and Tamassia, R. Checking the convexity of polytopes and the planarity of subdivisions. Computational Geometry: Theory and Applications 11, 3-4 (1998), 187-208. [ pdf ]

Goodrich, M. T., and Tamassia, R. Data Structures and Algorithms in Java, first ed. Wiley, New York, NY, 1998.

Goodrich, M. T., and Tamassia, R. Dynamic Trees and Dynamic Point Location. SIAM Journal on Computing 28, 2 (1998), 612-636. [ pdf ]

Liotta, G., Preparata, F., and Tamassia, R. Robust proximity queries: An illustration of degree-driven algorithm design. SIAM Journal on Computing 28, 3 (1998), 864-889. [ pdf ]

Tamassia, R. Constraints in Graph Drawing Algorithms. Constraints 3, 1 (1998), 89-122. [ pdf ]

Tamassia, R. Implementing Algorithms and Data Structures: an Educational and Research Perspective. In Proceedings of the Annual International Symposium on Algorithms and Computation (1998), Springer-Verlag, pp. 4-8. [ pdf ]

Chiang, Y.-J., and Tamassia, R. Optimal Shortest Path and Minimum-Link Path Queries Between Two Convex Polygons Inside a Simple Polygonal Obstacle. International Journal of Computational Geometry and Applications 7, 1-2 (1997), 85-121. [ pdf ]

Cohen, R. F., and Tamassia, R. Combine and Conquer. Algorithmica 18 (1997), 342-362. [ pdf ]

Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., and Vargiu, F. An Experimental Comparison of Four Graph Drawing Algorithms. Computational Geometry: Theory and Applications 7, 5-6 (1997), 303-325. [ pdf ]

Goodrich, M. T., and Tamassia, R. Dynamic Ray Shooting and Shortest Paths via Balanced Geodesic Triangulations. Journal of Algorithms 23 (1997), 51-73. [ pdf ]

Kant, G., Liotta, G., Tamassia, R., and Tollis, I. G. Area Requirement of Visibility Representations of Trees. Information Processing Letters 62, 2 (1997), 81-88.

Tamassia, R., Vismara, L., and Baker, J. E. A Case Study in Algorithm Engineering for Geometric Computing. In Proceedings of the Workshop on Algorithm Engineering (Sep 1997), pp. 136-145. [ pdf ]

Tamassia, R., and Cantrill, B. Data Structures. In Handbook of Computer Science and Engineering, A. B. T. Jr., Ed. CRC Press, 1997, pp. 86-110.

Tamassia, R. Graph Drawing. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, Eds. CRC Press LLC, Boca Raton, FL, 1997, pp. 815-832.

Di Battista, G., and Tamassia, R. On-Line Maintenance of Triconnected Components with SPQR-Trees. Algorithmica 15 (1996), 302-318. [ pdf ]

Di Battista, G., and Tamassia, R. On-Line Planarity Testing. SIAM Journal on Computing 25, 5 (1996), 956-997. [ pdf ]

Eades, P., Lin, X., and Tamassia, R. An Algorithm for Drawing a Heirarchical Graph. International Journal of Computational Geometry and Applications 6, 2 (1996), 145-156. [ pdf ]

Tamassia, R. Data Structures. ACM Computing Surveys 28, 1 (1996), 23-26.

Tamassia, R. Graph Drawing. In Handbook of Computational Geometry, E. Goodman and J. O'Rourke, Eds. CRC Press, 1996.

Tamassia, R. On-Line Planar Graph Embedding. Journal of Algorithms 21, 2 (1996), 201-239. [ pdf ]

Tamassia, R., and Vitter, J. S. Optimal Cooperative Search in Fractional Cascaded Data Structures. Algorithmica 15, 2 (1996). [ pdf ]

Garg, A., Goodrich, M. T., and Tamassia, R. Planar Upward Tree Drawings with Optimal Area. International Journal of Computational Geometry and Applications 6, 3 (1996), 333-356. [ pdf ]

Tamassia, R., Liotta, G., and Preparata, F. P. Robust proximity queries in implicit Voronoi diagrams. In Proceedings of the 8th Canadian Conference on Computational Geometry (1996), p. 1. [ pdf ]

Tamassia, R., Agarwal, P., Amato, N., Chen, D., Dobkin, D., Drysdale, R., Fortune, S., Goodrich, M. T., Hershberger, J., O'Rourke, J., Preparata, F., Sack, J.-R., Suri, S., Tollis, I., Vitter, J., and Whitesides, S. Strategic directions in computational geometry. ACM Computing Surveys 28, 4 (1996), 591-606. [ pdf ]

Tamassia, R. Constraints in Graph Drawing. In Proceedings of the International Workshop on Constraints for Graphics and Visualization (1995), p. 85.

Tamassia, R., and Tollis, I. G. Reachability in Planar Digraphs with One Source and One Sink. Theoretical Computer Science 119 (1993), 331-343.

Tamassia, R. A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps. In Abstracts 8th European Workshop on Computational Geometry (1992), Utrecht University, p. 39. [ pdf ]

Tamassia, R. An incremental reconstruction method for dynamic planar point location. Information Processing Letters 37 (1991), 79-83.

Tamassia, R., Tollis, I. G., and Vitter, J. S. Lower Bounds and Parallel Algorithms for Planar Orthogonal Grid Drawings. In Proceedings of the IEEE Symposium on Parallel and Distributed Processing (1991), pp. 386-393. [ pdf ]

Tamassia, R., and Vitter, J. S. Parallel transitive closure and point location in planar structures. SIAM Journal on Computing 20, 4 (1991), 708-725. [ pdf ]

Tamassia, R., and Tollis, I. G. Representations of Graphs on a Cylinder. SIAM Journal on Discrete Mathematics 4, 1 (1991), 139-149. [ pdf ]

Tamassia, R. Drawing Algorithms for Planar st-Graphs. Australasian Journal of Combinatorics 2 (1990), 217-235.

Tamassia, R., and Preparata, F. P. Dynamic maintenance of planar digraphs, with applications. Algorithmica 5 (1990), 509-527.

Tamassia, R., and Vitter, J. S. Optimal Cooperative Search in Fractional Cascaded Data Structures. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (1990), pp. 307-316. [ pdf ]

Tamassia, R. Planar Orthogonal Drawings of Graphs. In Proceedings of the IEEE International Symposium on Circuits and Systems (1990).

Tamassia, R., and Vitter, J. S. Optimal parallel algorithms for transitive closure and point location in planar structures. In Proceedings of the International Workshop on Discrete Algorithms and Complexity (Fukuoka, Japan, Nov 1989), Institute of Electronics, Information and Communication Engineers (IEICE), Tokyo, pp. 169-178.

Tamassia, R., and Tollis, I. G. Planar Grid Embedding in Linear Time. IEEE Transaction on Circuits and Systems CAS-36, 9 (1989), 1230-1234.

Tamassia, R., and Tollis, I. G. Tessellation Representations of Planar Graphs. In Proceedings of the 27th Allerton Conference on Communication, Control, and Computing (1989), pp. 48-57.

Tamassia, R., Di Battista, G., and Batini, C. Automatic Graph Drawing and Readability of Diagrams. IEEE Transactions on Systems, Man and Cybernetics SMC-18, 1 (1988), 10-21.

Tamassia, R. A Dynamic Data Structure for Planar Graph Embedding. In Proceedings of the 15th International Colloquium on Automata, Languages and Programming (ICALP) (1988), T. Lepisto and A. Salomaa, Eds., Springer-Verlag, pp. 576-590.

Tamassia, R., and Tollis, I. G. Centipede Graphs and Visibility on a Cylinder. In Proceedings of the International Workshop on Graph Theoretic Concepts in Computer Science(WG '86 ) (Jun 1987), G. Tinhofer and G. Schmidt, Eds., Springer-Verlag, pp. 252-263.

Tamassia, R., and Tollis, I. G. Efficient Embedding of Planar Graphs in Linear Time. In Proceedings of the IEEE International Symposium on Circuits and Systems (1987), pp. 495-498.

Tamassia, R. On Embedding a Graph in the Grid with the Minimum Number of Bends. SIAM Journal on Computing 16, 3 (1987), 421-444.

Tamassia, R., and Tollis, I. G. A Unified Approach to Visibility Representations of Planar Graphs. Discrete and Computational Geometry 1, 4 (1986), 321-341.

Tamassia, R. New Layout Techniques for Entity-Relationship Diagrams. In Proceedings of the 4th International Conference on Entity-Relationship Approach (1985), pp. 304-311.

All publications by Roberto Tamassia

Edit this page

Page Owner: Roberto Tamassia

Last Modified: Tue Sep 9 10:59:21 2008

Inside Search:

Roberto Tamassia

Contact Information

Research Areas

Research Themes

Research Topics or Projects

Courses Taught

Research Interests

Selected Publications