Speakers

Heuristics in Graph Drawing

Information systems are nowadays commonly represented with a drawing, which makes them easier to interpret and understand. Graphs are the basic modeling unit in a wide variety of areas in computer science and operations research. This is why graph drawing has become an important research area, with a large number of publications and resources. The selection of a measure or criterion to evaluate the quality of a graph drawing is somehow controversial given the many different approaches to this problem. We can identify in the scientific literature several drawing standards, and different criteria that lead to difficult optimization problems.

In this talk we first give an overview of the graph drawing area, its aesthetic criteria and current approaches. Then, we focus on two challenging optimization problems, the incremental and the min-max crossing problems. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic, where we seek to preserve the layout of a graph over successive drawings. We consider the edge crossing reduction in the context of incremental graph drawing. Another interesting variant was recently identified in the context of VLSI circuits in which it is more appropriate to minimize the maximum number of crossings over all edges (min-max problem) than minimizing the traditional sum of crossings. We describe metaheuristic algorithms for these problems and illustrate its performance on different examples.