**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)