Research Projects

	GraphSET is our Graph Simultaneous Embedding Tool. We developed this software in order to have a pracatical way to study several types of problems in simultaneous graph embeddings: simultaneous geometric embedding, simultaneous embedding with fixed edges, and colored simultaneous embedding. GraphSET can be used to study theoretical problems in simultaneous graph drawing and to produce drawings from known algorithms for these problems. The software and the code are available for download together with a user guide, screenshots, and simultaneous embedding challenges.
	SMorph: Spherical Graph Morphing SMorph is a project that deals with morphing of graph drawings on the surface of the sphere. We are interested in the problem of intersection-planar graph morphing, and in particular, a generalization from Euclidian space to spherical space. We show that under certain conditions, there exists a continuous and intersection-free morph between two sphere drawings of a maximally planar graph, where sphere drawings are the spherical equivalent of plane drawings: crossings-free geodesic-arc drawings. In addition to the existence proof, we describe a morphing algorithm along with its implementation.
	GRIP: Graph Drawing with Intelligent Placement GRIP is designed for drawing large graphs and uses a novel multi-dimensional force-directed method together with fast energy function minimization. The algorithm underlying the system employs a simple recursive coarsening scheme. Rather than being placed at random, vertices are placed intelligently, several at a time, at locations close to their final positions. The running time and space complexity of the system are near linear. The implementation is in C using OpenGL for 3D viewing. GRIP allows for drawing graphs with tens of thousands of vertices in under one minute on a mid-range PC. To the best of the authors' knowledge, GRIP surpasses the fastest previous algorithms. However, speed is not achieved at the expense of quality as the resulting drawings are quite aesthetically pleasing. For a sample of what GRIP does, take a look a few animated examples.
	TGRIP: Temporal Graph Drawing TGRIP is an application designed for interactive visualization of large weighted graphs that have a temporal component. TGRIP is designed for drawing large graphs and uses a novel multi-dimensional force-directed method together with fast energy function minimization. The algorithm underlying the system employs a simple recursive coarsening scheme. Rather than being placed at random, vertices are placed intelligently, several at a time, at locations close to their final positions. In most applications it is necessary to be able to visualize graphs in which vertices/edges have weights. The layout component should take into account these weights while doing the placement. A pair of vertices connected with a large weighted edge should be placed closer to each other than another pair with smaller edge weight for example. TGRIP handles this by introducing the weight concept to the general force-directed method. The graphs that we are interested in evolve through time. The changes in the graph include adding and removing vertices/edges. TGRIP allows us to control the tradeoff between readable drawings and mental map preservation between consecutive drawings. Finally, the system generates smooth animations between consecutive time steps.
	GraphAEL: Graph Animations with Evolving Layouts GraphAEL extracts three types of evolving graphs from the Graph Drawing literature and creates 2D and 3D animations of the evolutions. We study citation graphs, topic graphs, and collaboration graphs. We also create different graphs which capture the nature of change between two given time periods.
	graphael graphael is a system that implements several classic force-directed layout methods, as well as several novel layout methods for non-Euclidean geometries, including hyperbolic and spherical. The system can handle large graphs, using multi-scale variations of the force-directed methods. Finally, the system can layout and visualize graphs that evolve though time, using static views, animation, and morphing. The current system is equipped with a core package of force-directed algorithms and visualization tools. In addition to putting together well-known algorithms and visualization methods, graphael contains several novel features. Some of these features include support for temporal graphs, interactive graph visualization, multi-scale layout algorithms for large graphs, and embedding graphs in non-Euclidean spaces, such as hyperbolic space and spherical space.
	TetraTetris TetraTetris is a multi-user game utilizing a DiamondTouch table. The DiamondTouch table is a touch-sensitive input device that allows several users to interact with a program at the same time and do so using their hands. We describe our exploration of the capabilities and limitations of the DiamondTouch by focusing on TetraTetris, one of the first nontrivial applications written specifcally for the DiamondTouch hardware. TetraTetris is a multi-player game, loosely based on the popular game Tetris, in which players use their hands to manipulate objects moving around on the table; it illustrates some of the table's key advantages and drawbacks by comparison with conventional input hardware. In this paper we describe the DiamondTouch hardware, the rules of TetraTetris, the problems we encountered implementing it, and what TetraTetris can show us about the future of input devices like the table.
	Simultaneous Embedding Simultaneous Embedding is a new graph theoretical problem. This project deals with the simultaneous embedding of multiple planar graphs. The goal is to produce aesthetically pleasing drawings for the two graphs by means of a heuristic algorithm and with human assistance. Our implementation uses the DiamondTouch table, a multi- user, touch-sensitive input device, to take advantage of direct physical interaction of several users working collaboratively. The system can be downloaded or the corresponding applet can be used online.
	GMorph: Intersection Free Morphing of Planar Graphs GMorph is an implementation of an algorithm for morphing of planar graphs. Morphing refers to the process of transforming one shape (the source) into another (the target) In planar graph morphing we would like to transform a given source graph to another pre-specified target graph. A smooth transformation of one graph into another can be useful for numerous problems from graph drawing. In particular, when dealing with dynamic graphs and graphs that change through time, it is crucial to preserve the mental map of the user. Thus, it is important to minimize the changes to the drawing and to create a smooth transition between consecutive drawings. Another important goal is to avoid creating any intersections throughout the morph. We designed and implemented an algorithm that can morph between drawings with straight-line segments, bends and it relies on a combination of techniques to achieve smooth transformations: rigid morphing, compatible triangulations, as well as morphing based on interpolation of the convex representations of the graphs. Here is a short (5 min) but large (200MB+) video overview of the project.
	SIMG: Simultaneous Graph Drawing Consider the problem of drawing and displaying a series of related graphs that share all or parts of the same vertex set. The graphs may represent different relations between the same set of objects. SIMG illustrates different approaches to simultaneous graph drawing. We have developed and implemented three different techniques for laying out a series of graphs to be simultaneously embedded. We have also designed and implemented three different schemes for visualizing multiple graphs. While each of these visualization schemes corresponds closely to one of our layout algorithms, any combination of a layout algorithm and a visualization scheme can be used. When visualizing a series of graphs that share all or parts of the same vertex set, it is important to display the graphs in such a way that the user can either focus on one graph at a time without being confused by the other graphs in the series or visualize the layouts of multiple graphs at the same time to get a mental map between the different relations represented by each graph.
	Fat-Edges Graph Drawing Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this paper we consider the problem of drawing graphs with edges of variable thickness. The thickness of an edge is often used as a visualization cue, to indicate importance, or to convey some additional information. We present a model for drawing with fat edges and a corresponding polynomial time algorithm that uses the model. A short movie and paper illustrate the algorithm.
	SPLaT: Self-Plagiarism Tool SPLat is a tool for self-plagiarism detection. The current version of SPlaT functions as a web spider that crawls through the web sites of fifty Computer Science departments, downloading research papers to search for instances of self-plagiarism by Computer Science academics. Instances of self-plagiarism for each author are reported so that they may be investigated in order to determine if they are truly fraudulent papers.