University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Graduation Talks

title

Constrained Graph Drawing

speaker

Barbara Pampel, University Konstanz
Konstanz, Germany

date & place

Wednesday, 11.11.2009, 16:15 h
Room C252

abstract

Graphs are widely used to visualize relational data. The utility of a drawing depends on aesthetic criteria, such as vertex distribution and planarity, as well as on the amount of information contained in the data that can be revealed by the drawing. Information can be assigned to the elements, vertices and edges, but also be displayed through their absolute and relative position. With the help of geometric constraints the graphs can meet the different requirements of concrete applications. In this thesis various types of constraints are studied on relevant classes of graphs. While efficient algorithms have been obtained for some cases others led to hardness results.