Academics
Contents
My Research
Graph Drawing and Computational Geometry Resources
Algorithms Resources
My Research

I'm a sixth year student in the PhD program at Brown University, and I expect to be finishing in the summer of 2001. My research has primarily been in the area of graph drawing, though I am also interested in information visualization, computational geometry, and Internet computing.

Graph Drawing

A graph in this sense is the mathematical sort of graph representing objects and relationships between them, not pie charts and bar graphs like you might get from Microsoft Excel. The type of graph I'm talking about might represent all of the flights for a particular airline - the vertices of the graph represent the cities the airline flies to, and the edges that connect the vertices represent flights connecting two cities.

Graph drawing is the art of taking a combinatorial representation of a graph - a list of the vertices and the edges that connect them - and producing a nice picture of it. In such a picture, vertices are typically represented by points or rectangular boxes and edges are drawn as lines connecting the points. Consider the drawing that you tend to find in the back of the inflight magazines that shows where the airline flies - that's a drawing of a graph.

What constitutes "nice", of course, varies with the application. In the case of the flight graph, you probably want to put each vertex near the geographical location of the city and the principle problem is how to draw the edges without creating a jumble of criss-crossing edges. For more abstract graphs, though, there may not be a predefined location for the vertices - if your graph represents a collection web pages on a web site and the links between them, how do you place the vertices? You might want to try to maximize the display of symmetries in the graph, or to cluster closely related vertices - the latter might be particularly useful if you are trying to analyze the web site and determine if there is any hidden structure. Maybe you want all of the edges to be drawn as straight lines, or the graph should be drawn on a grid. You could also want to minimize the area covered by the drawing or the number of edge crossings and bends.

What makes graph drawing an interesting area is that the optimization goals such as area and number of bends are typically NP-hard, and that various drawing conventions and goals tend to contradict each other - not only can you not always solve the problems optimally and quickly, but producing a drawing that excels in one respect may reduce its quality in another.

My first (and current) project was (is) the Graph Drawing Server, a Web-accessible server for graph drawing algorithms. Many implementations of graph drawing algorithms exist, but for someone to make use of such an implementation can be an involved process. First, you have to know enough about graph drawing to determine what algorithm you might want to use. Then you have to find an implementation (or implement it yourself, which may well be a non-trivial task), download and compile it (hoping all the while that it will run on your system), and then, since there is not a commonly accepted file format for graphs, learn the format used for this program and translate all of your data to that format. This is a significant obstacle, and the goal of the Graph Drawing Server is to make implementations of graph drawing algorithms available to a wide audience, allowing practitioners to "shop around" for an appropriate algorithm and researchers to compare performance of different algorithms. In addition to the actual drawing algorithms, the server provides a translation feature to convert graphs between different file formats; translation can happen implicitly as part of a drawing request or explicitly to simply convert a file.

The current project with the Graph Drawing Server is to reimplement it, to take advantage of the new possibilities in Java and to better support the idea of "cooperative computing" (described in more detail under "GeomNet", below).

If the server is down and you can't access this page, or you can access the page but the applet interface can't contact the server, let me know and I'll restart things as soon as possible.

Nothing in the Graph Drawing Server's architecture limited it to graph drawing algorithms as such, and it evolved into GeomNet, a joint project with a group at Johns Hopkins University. GeomNet expanded the vision for the Graph Drawing Server into a collection of geometric algorithm servers, which could communicate with each other and the client in order to perform computational geometry computations. (However, nothing in the system limits it to just computational geometry algorithms either.) The current implementation of GeomNet uses as architecture similar to the Graph Drawing Server, where the division of work is sharply partitioned - the (presumably fast) server runs the algorithms and the (presumably resource-limited) client handles only the user interface. In the plans for GeomNet, however, was the idea of "cooperative computing", where the client and server could negotiate the best distribution of algorithm code so as to balance CPU speed and network speed - for a fast client and a slow network, it might be more efficient to send the algorithm code to the client once and have it execute there instead of continually sending the data to the server, whereas for a slow client and a fast network, it might be faster to always send the data to the server and run the algorithm there.

The two main goals of the Graph Drawing Server/GeomNet reimplementation project are to add support for cooperative computing and to add security. For the first goal, the objective is to add the framework that allows code to travel, and to leave research into how best to negotiate the division of labor to a future project. For the second, the plan is to provide authentication abilities so that individual servers can limit which clients are allowed to use their services, and to protect the result of one client's computation from access by other clients. This will make it possible to deploy algorithms in the system without making them world-usable - for example, a company may want to run one or more GeomNet servers for its employees, without letting the entire world use the service. It will also allow sensitive data to be sent to a trusted server without the risk of being read by outsiders.

(The Geometric Algorithm Server component of GeomNet is currently offline, but the Graph Drawing Server is running.)

InteractiveGiotto

InteractiveGiotto is an algorithm for interactive orthogonal graph drawing. In orthogonal drawings, vertices are placed on grid points and edges consist of horizontal and vertical segments along grid lines. Most graph drawing algorithms redraw the graph from scratch at each step, making them undesirable for applications where a user repeatedly makes small modifications to a graph and wants to produce a new drawing at each step. Completely rearranging the picture destroys the user's "mental map" and requires that the user invest time in re-learning the drawing after each step. Interactive drawing algorithms take the previous drawing into account and attempt to preserve the mental map while still producing a good drawing. InteractiveGiotto is a wrapper around the successful orthogonal graph drawing algorithm Giotto, which uses flow networks to minimize the number of edge bends and the total area of the graph. InteractiveGiotto takes a drawing as input (instead of the usual description of a graph, without geometry attached) and works by applying constraints to force Giotto to keep certain aspects of the original graph intact. These constraints are of two types - preserving the number and direction of bends in the edges, and preserving the angle between consecutive edges around each vertex. Much of the initial work of applying the constraints was done by Jody Fanto; I added a bit to allow the user to relax some of the constraints to obtain better drawings, and adapted the editor interface for the Graph Drawing Server to allow this sort of interaction.

Similarity Measures for Graph Drawing

Work with InteractiveGiotto has also lead to research into similarity measures to describe the degree of similarity (or lack thereof) between different drawings of the same graph (or nearly the same graph). The initial motivation for this work was a problem with InteractiveGiotto - the Giotto blackbox at the core of InteractiveGiotto throws away coordinates when computing a new drawing, with the result that the final drawing could be rotated by a multiple of 90 degrees with respect to the original drawing. Unfortunately, even if the two drawings are very similar to each other, a large rotation can confuse the user and destroy the mental map. So we needed a quick fix to pick the "correct" rotation... Enter the quest for similarity measures, since an obvious solution would be to try all the possible rotations (there are only four, after all) and choose the one most similar to the original drawing. No one (to my knowledge) has done a comprehensive study of possible similarity measures - most work with interactive graph drawing algorithms has been based on intuitive models of similarity and comes down to "the algorithm does a good job because it doesn't move stuff much". My research has focused on trying to formally define possible similarity measures and then testing them in user studies, to see if the models match what people are seeing.

Compaction of Orthogonal Representations

Consider a collection of small blocks connected to each other with dowels stuck into holes drilled on the four sides of the blocks. (Consider the problem only in 2D - dowels cannot be stuck on the top or bottom sides of the blocks.) The dowels have been glued into the holes, so the clockwise order of the dowels and the angle between two consecutive dowels around the block cannot be changed. The dowels are rigid and so cannot be bent, but are telescoping and can be adjusted in length from one unit to arbitrarily long. The one complication here is that the dowel lengths can only be set to whole units, so a dowel can be one unit or two units long, but not 1.5 units. The problem is to adjust the dowel lengths so as to minimize the area of the smallest rectangle containing all of the blocks and edges and/or the total length of all of the dowels. The name "compaction" stems from this minimization goal.

To apply this to graph drawing, "compaction" is the third phase in the topology-shape-metrics approach to orthogonal graph drawing, used by algorithms like Giotto. In the topology step, the embedding of the graph is fixed - the graph is made planar by inserting dummy vertices at edge crossings, and the order of edges around each vertex is fixed. In the shape step, the angles between consecutive edges around each vertex and the number and direction of bends along each edge are fixed, but no edge lengths or coordinates are assigned. The result of the shape step is an orthogonal representation. The compaction phase finally assigns edge lengths/coordinates to produce an orthogonal drawing, usually with the goal of minimizing the area and/or total edge length in the drawing. Compaction problems also arise in VLSI layout applications. The minimization goals are NP-hard in general, but we characterized a non-trivial class of orthogonal representations for which compaction can be done optimally in polynomial time, and developed improved heuristics for compaction based on this definition.

Graph Drawing and Computational Geometry Resources
This is by no means a comprehensive list of sites; instead it is a hodgepodge of things that I have come across which serves as useful entry points. Things are grouped roughly into categories to aid in exploration, but many sites have information in multiple categories and most sites have at least a small collection of links to other sites.

Graph Drawing

Introductory material

Journals and Papers

Tools and Software

(These are all graph-related, but some of the software libraries may not be specifically for graph drawing.)

Applications

Conferences

Centers

Link Collections

Computational Geometry

Journals

Mailing Lists

Tools

Applications

Conferences

Centers

Link Collections

Algorithms Resources

Resources related to algorithms:

Home Useful Things Fun Things

ssb@cs.brown.edu -- last update: 9/28/2000