http://www.dagstuhl.de/08191

May 4 – 9, 2008, Dagstuhl Seminar 08191

Graph Drawing with Applications to Bioinformatics and Social Sciences

Organizers

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)


For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl's Impact: Documents available

Summary

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

Classification

  • Computer Graphics / Visualization / Human-computer-interaction

Keywords

  • Graph drawing
  • Usability

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, 1st floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.