04. – 09. Mai 2008, Dagstuhl-Seminar 08191

Graph Drawing with Applications to Bioinformatics and Social Sciences


Stephen P. Borgatti (University of Kentucky – Lexington, US)
Stephen G. Kobourov (University of Arizona – Tucson, US)
Oliver Kohlbacher (Universität Tübingen, DE)
Petra Mutzel (TU Dortmund, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
Dagstuhl's Impact: Dokumente verfügbar


Graph drawing deals with the problem of communicating the structure of relational data through diagrams, or drawings. Graphs with vertices and edges are typically used to model relational data. The vertices represent the objects (or data points) and the edges represent the relationships between the objects. The main problem in relational visualization is to display the data in a meaningful fashion that may heavily depend on the application domain. Some of the application areas where graph drawing tools are needed include computer science (data base design, data mining, software engineering), bioinformatics (metabolic networks, protein-protein interaction), business informatics (business process models), and the social sciences and criminalistics (social networks, phone-call graphs).

The ability to represent relational information in a graphical form is a powerful tool which allows us to perform analysis through visual exploration. With the aid of graph visualization we can find important patterns, trends, and correlations. Real-world applications such as bioinformatics and sociology pose additional challenges, e.g., semantic information carried by the diagram has to be used for obtaining meaningful layouts and application-specific drawing conventions need to be fulfilled. Moreover, the underlying data often stems from huge data bases, but only a small fraction shall be displayed at a time; the user interactively selects the data to be displayed and explores the graph by expanding interesting and collapsing irrelevant parts. This requires powerful graph exploration tools with navigation capabilities that allow dynamic adaption of the graph layout in real time.

Topics of the Seminar

In this seminar we focused on the application of graph drawing in two important application domains: bioinformatics (metabolic pathways, regulatory networks, protein-protein interaction)and social sciences and criminalistics (case information diagrams, phone-call graphs). In both application domains, the underlying information is usually stored in large data bases constituting a huge and complex graph, but only a suitable fraction of this graph is visualized; the selection of that subgraph is guided by the user and even more user interaction occurs in order to further explore the underlying graph. Thus, the user becomes a central actor that triggers dynamic updates of the displayed graph and its layout. The support of application-specific update functionality in conjunction with high quality graph layout is essential for achieving user acceptance in the targeted application areas.

The interactive navigation through the graph poses new challenges to graph drawing algorithms. Whereas traditional graph drawing deals with the visualization of static graphs, we are now concerned with graphs that change over time, and the layout has to be adjusted in real time. The new layout has to observe aesthetic and application specific drawing criteria, as well as the preservation of the user's mental map; in particular only few changes in the layout are desired.

A similar dynamic component occurs in the visualization of graphs that evolve over time like minute-by-minute phone-call graphs which have application in police investigations. Here, we have a graph at each time point and an edge corresponds to a phone call between two telephones. In contrast to interactive navigation, we know in advance all of the changes the graph will undergo, and we can exploit this fact for producing a smoother animation sequence.

In summary, it is our impression that the participants enjoyed the great scientific atmosphere offered by Schloss Dagstuhl, and pro ted from the scienti c program. We are grateful for having had the opportunity to organize this seminar. Special thanks are due to Carsten Gutwenger and Karsten Klein for their assistance in the organization and the running of the seminar.

Dagstuhl-Seminar Series


  • Computer Graphics / Visualization / Human-computer-interaction


  • Graph drawing
  • Usability


Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.