(1) Departamento de Matemática Aplicada, Facultad de
Informática, Universidad Politécnica de Madrid, Spain.
{mabellanas, gregorio}_AT_fi.upm.es
(2) Departamento de Computación, Facultad de Ciencias Exactas
y Naturales, Universidad de Buenos Aires, Argentina.
{aaiello, rsilveir}_AT_dc.uba.ar
(Warning: this page is under construction)
Introduction
The problem known as graph drawing consists in finding a
drawing of a given graph that is visually pleasant, based on some aesthetic criteria.
In the
last fifteen years the graph drawing community has witnessed a major explosion in the number of publications related to
graph drawing, covering hundreds of specific problems that arise in different
areas, whose common denominator is that there is always some kind of graph that
needs to be visualized.
In this work we concentrate on a concrete and unexplored graph drawing problem: the one arising when each vertex of the graph represents a geographical region. The figure at the top of this page shows an example, where each node of the graph represents a region of Spain, and edges represent data links between them. The purpose of the drawing is to show in a clear manner which pairs of regions are connected by (direct) data links.
There are many different situations where algorithms for drawing these kinds of graphs are needed. As a second example, consider the case when there is a company trying to understand the way each office's employees collaborate with each other. The information can be modeled with a graph, where each node represents an office (hence each of them has a geographical region associated). Two offices would be connected if and only if their employees work together. As in the previous example, a good layout out of this graph needs to show clearly the relation between the regions, i.e. which pairs of offices collaborate with each other.
When dealing with graphs whose vertices represent geographical regions, we must ensure that (1) each node is located inside its region and that (2) each node represents its region. This second, somewhat vague, point turns out to be specially important if what we are looking for is an aesthetically pleasant layout of the graph.
Although several authors have studied how to adapt graph drawing algorithms to take into account constraints in the position of vertices, ensuring that no vertex is placed outside its region is not enough to produce good drawings, since it might not be clear enough what is the region represented by each vertex.
In order to design appropriate algorithms for this problem, we first define new aesthetic criteria. Secondly, several force-directed algorithms for finding layouts that satisfy those specific criteria are proposed, which successfully obtain much better drawings for this problem than the previous algorithms. In this page we describe briefly the proposed criteria and algorithms. A Java application, also available in this page, demonstrates the effectiveness of the proposed algorithms.
This page contains only some few results from our work. In the near future a more detailed article will be available. In the meantime, more details can be found in this dissertation (in Spanish).
New aesthetic criteria
From now on, we will suppose that every node represent exactly one region, and that regions don't overlap each other. Furthermore, we will use a polygon to describe each vertex's region. In what follows, G=(V,E) denotes a graph with set of vertices V and set of edges E.
Graph drawing algorithms are based on so-called aesthetic criteria, which specify what properties a good layout of a graph must have. Force-directed methods, which are among the most commonly used algorithms for graph drawing, usually try to satisfy two criteria: uniform edge length and uniform vertex distribution. In addition, some of them also try to avoid edge crossings. However, when nodes represent, and are constrained to, regions, these criteria are not as important (or as valid) as in the general graph drawing problem. For instance, we can't expect to get uniform edge length or uniform vertex distribution if the distance between regions is not uniform. In practice, this means that applying a standard graph drawing algorithm to a graph whose nodes represent regions (even if nodes are confined to their regions) will not produce good results. This motivates the search for new criteria.
In our analysis of possible aesthetic criteria, we found that two were particularly important:
C1. Nodes must be placed near the center of its regions.
C2. Nodes must not be placed near the borders of their regions.
In addition to identifying these two criteria, we noted that avoiding edge crossings is a very important factor in this problem, as it is in standard graph drawing. Once relevant criteria were defined, we designed algorithms to produce drawings addressing them.
Algorithms
In order to design algorithms to obtain good layouts, based on the aforementioned criteria, we decided to adapt some well-known force-directed algorithms to our specific problem. The ones chosen were Eades' spring embedder (SE) and the Simulated Annealing algorithm of Davidson and Harel (DH). The proposed algorithms were named SER2 and DHR2. Both of them are reviewed briefly below.
SER2
This algorithm extends Eades's spring embedder in order to fulfill the two new criteria.
First of all, the ideal length of edges (constant in the original algorithm) is redefined in order to take into account the distance between node's regions. For each pair of nodes, the ideal edge length for (u,v) in E is defined as:
lambda*distCenters(u,v) + (1-lambda)*minDistReg(u,v)
Where lambda is a number between 0 and 1 (we obtained good results with 0.5), distCenters(u,v) is the distance between the centroids of regions corresponding to u and v, and minDistReg(u,v) is the minimum distance between both regions.
Secondly, centripetal forces between each node and the centroid of its region were added, in order to address criterion C1. These forces have an effect similar to adding springs between the centroid of each region and its node.
DHR2
Our DHR2 algorithm extends Davidson and Harel's by adding several new potentials:
Two new potentials to avoid edge crossings. The first one penalizes short distances between edges (distance is defined as 0 for edges that cross). The second one aims at guiding the search algorithm to "undo" existing crossings. This is accomplished by penalizing the shortest distance between each one of the four involved nodes and the crossing point.
A potential to address criterion C2, that penalizes short distances between each node and its region. In order to make the effect of this potential more abrupt, an exponential function was used. This makes the potential very strong when the node is near the border, but decreases quickly as the node gets farther.
Java application
A Java application was built to show the results that can be obtained with each of these algorithms. Right now it is only available in Spanish, but a version in English will be posted here in the near future.
The application can be run both as an applet or as a Java application (.jar file, 990 KB), although in the first case, file operations will not work. A set of sample graphs (with regions defined), is also available, by clicking here (23 KB)). Sample graphs (.gml files) can be opened from the "Archivo/Abrir..." menu.
The application is very easy to use, and it is based on the VGJ environment. The most important thing that must be explained is how to define the region of a node.
Each region can be a disc or polygon. To define the region of a node, select it (first by clicking "Select nodes", then by clicking the node itself) and then press key D. The radius of the disc will be defined with the mouse cursor, and set with a click.
Polygons are entered in a similar way, but instead of pressing D, key P must be pressed. Each vertex of the polygon is set with a left button click. Once all vertices have been defined, press ESC to finish editing the polygon.
The "Algoritmos" menu allows to run both algorithms mentioned here, plus the classic SE and DH with the only addition that vertices are constrained to their regions.
Click here to run the application as a Java applet. If you want to run it as a Java application, download de .jar file and run it with the Java Virtual Machine (J2SE JRE, available form Sun's website). For any question or problem please contact us ({aaiello, rsilveir}_AT_dc.uba.ar).
Last update: 2004-Dic-02.