Graph Drawing

Many information systems require graphs to be drawn so that they are easy to read and understand. Graphs are used commonly as a basic modeling tool in areas such as project management, production scheduling, line balancing, business process reengineering, and software visualization. Graph drawing addresses the problem of constructing geometric representations of graphs. Although the perception of how good a graph is in conveying information is fairly subjective, the goal of limiting the number of arc crossings is a well-admitted criterion for a good drawing. We have studied several variants of the so-called graph drawing problem in which we basically consider the arc crossing minimization problem.

Incremental graph drawing constructions are motivated by the need to support the interactive updates performed by the user. It is helpful to preserve a "mental picture" of the layout of a graph over successive drawings. It can be distracting to make a slight modification, perform the graph drawing algorithm, and have the resulting drawing appear very different from the previous one. Therefore, generating incrementally stable layouts is important for many applications. Layout strategies that strive to preserve perspective from earlier drawings are called incremental. We have also consider this problem in several papers.

The following figure shows a graph from the Forrester's book (1971). Specifically, it shows the solution given by the Tabu Search algorithm with 38 crossings, which compares favorably with the GRASP solution with 44 crossings. The Barycenter algorithm with a switching post-processing obtains a solution with 78 crossings while the SemiMedian+Switching solution has 88 crossings.

Papers

Tabu Search for the Dynamic Bipartite Drawing Problem
R. Martí, A. Martínez-Gavara, J. Sánchez-Oro, A. Duarte Computers and Operations Research, In press

Variable Neighborhood Scatter Search for the Incremental Graph Drawing Problem
J. Sánchez-Oro, A. Martínez-Gavara, M. Laguna, R. Martí, A. Duarte Computational Optimization and Applications, In press

Heuristics and Meta-Heuristics for 2-Layer Straight Line Crossing Minimization
Rafael Martí and Manuel Laguna, Discrete Applied Mathematics 127 (3), 665-678 (2003)

Arc Crossing Minimization in Graphs with GRASP
Rafael Martí, IIE Transactions 33 (10), 913-919 (2001)

Incremental Bipartite Drawing Problem
Rafael Martí and Vicente Estruch, Computers and Operations Research 28, 1287-1298 (2001)

GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
Manuel Laguna and Rafael Martí, INFORMS Journal on Computing 11(1), 44-52 (1999).

A Tabu Search Algorithm for the Bipartite Drawing Problem
Rafael Martí, European Journal of Operational Research 106, 558-569 (1998).

Arc Crossing Minimization in Hierarchical Digraphs with Tabu Search
M. Laguna, R. Martí and V. Valls, Computers and Operations Research 24(2), 1175-1186 (1997)

A Tabu Thresholding Algorithm for Arc Crossing Minimization in Bipartite Graphs
V. Valls, R. Martí and P. Lino, Annals of Operations Research 63, 233-251 (1996)

A Branch and Bound Algorithm for Arc Crossing Minimization in Bipartite Graphs
V. Valls, R. Martí and P. Lino, European Journal of Operational Research 90, 303-319 (1996)