Straight-Line Grid-Drawings of Planar Graphs

Project Members


Visualization is a central aspect to many problems which can be modeled using graphs. Drawing the edges of a planar graph as straight lines without crossings is among the common aesthetic criteria. It is also common to require that the vertices of the graph be drawn on an integer grid. Certain problems occurring in the design of integrated circuits can be modeled as a graph drawing problem. In this context, minimizing the area of such drawings is essential. We are interested in both theoretic and algorithmic aspects of the problem. We could show that the problem of minimizing the area of planar straight-line grid drawings is NP-hard, and we have developed an algorithm for the compaction of planar straight-line grid drawings. In addition to that we are working on approximation algorithms as well as on optimal exponential-time algorithms for small problem instances.