Adam Buchsbaum, Emden Gansner, Cecilia Procopiuc, Suresh Venkatasubramanian

The project addresses the problem of visualizing database schemata. A schema of a relational database can be naturally represented as a graph, with the nodes corresponding to entities and the edges representing relations. Directed edges reflect a one-to-many relation from tail to head. For purposes of understanding and navigating the schema, it can be useful to draw the schema as a graph. Traditional graph drawings, however, with edges drawn as line segments, can use too much space and appear too cluttered, especially if used as part of a user interface where the nodes serve as buttons. An alternative drawing can be based on rectangular layouts and contact graphs, in which two nodes sharing an edge are placed abutting each other. If an edge is directed, one can require the additional constraint that the drawing honor edge directions in the sense that the head node must appear to the right or below the tail node. We have been working on the algorithmic aspects of generating such drawings. We have derived various existence and complexity results, and have constructed efficient heuristics for generating such drawings in both the undirected and directed cases, especially for the important case when the underlying (undirected) graph is a tree.

<< Back to Projects & Software