Automated graph drawing deals with the layout of relational data arising from computer science (database design, data mining, software engineering) and other sciences such as bioinformatics and sociology (social networks). The relational data are typically modeled as graphs, which can be visualized through diagrams drawn in the plane. The main objective is to display the data in a meaningful fashion, that is, in a way that shows well the underlying structures, and that often depends on the application domain. Although high quality algorithms exist for many optimization problems that arise in graph drawing, they are often complex and difficult to implement, and theoretically efficient algorithms may show an unacceptable runtime behavior even for small to medium real world instances. Also large graphs like, e.g., molecular interaction networks may render exact but complex algorithms infeasible and require approximate or heuristic solutions.

Integrating automated graph drawing techniques into real-world software systems poses several algorithm engineering challenges. To achieve effective implementations, algorithms and data structures designed and analyzed on abstract machine models must be carefully tuned for performance on real hardware platforms. This task is becoming increasingly more difficult due to the impressive growth of data to be visualized in modern applications, as well as their highly dynamic and data-intensive nature. Developers can no longer ignore architectural aspects such as the presence of complex memory hierarchies and multiple cores, which are likely to shape the design of novel algorithmic techniques and the way they will be implemented and engineered in the future.

The aim of this seminar was to bring together researchers from the algorithm engineering and graph drawing communities in order to strengthen and foster collaborations in this area and to identify key research directions for the future.

The seminar was attended by 48 participants from both academia and industry. Much was accomplished, fostered by the productive atmosphere of the Dagstuhl Center. Here we describe some of the more important achievements. The program consisted of a wide variety of presentations, working group sessions and discussion sessions.

Beyond the survey lectures, highlights of the seminar included the two introductory sessions, the open problem sessions, and the working groups. In two sessions, we have identified over two dozen open problems, which later crystallized into about a dozen well-defined problems, each of which were of interest to several participants. We had working groups on the following topics: Rotating binary trees, feedback arc set convergence, edge bundling models, co-occurence in bipartite graphs, RAC drawings, BRAC drawings, minimum branch spanning tree, cluster tree embedding, point set embeddings, parallel graph drawing, and library of graphs. Participants shared ideas and material using the online seminar Wiki. The dissemination sessions at the end of the workshop showed that many of the working groups have achieved initial results, which may lead to future publications. Arguably the most-appreciated features of the Seminar were the lively open discussion sessions, which led to several concrete proposals for the future of the field which, as a result of the workshop, are now being actively pursued.

A big step forward has been done concerning an online library of graphs. The graph drawing community would like to have such a library, however, there was no consensus about the requirements on such a graph archive. The working group conducted a survey on requirements for a graph archive during the Dagstuhl seminar. Two groups (Dortmund and Tübingen) presented their ideas and prototypes of such an archive. In order to foster future work and to encourage participation and contributions, it was suggested that the GD proceedings should offer the opportunity to publish papers concerning the library. Moreover, the collection of many benchmark graphs has already begun.

We used the opportunity to bring together experts in algorithm engineering for multi-core algorithms with graph drawing researchers in order to discuss how graph drawing algorithms can be re-engineered to better take advantage of modern computer architecture into account. This working group was inspired by the many different backgrounds of group members. They have discussed how to improve data locality, or exploit multi-core processors, in particular for the widely used Sugiyama drawing method. Subjectively (from interacting with the attendees) and objectively (from the official feedback data) we believe that the participants enjoyed the great scientific atmosphere offered by Schloss Dagstuhl, and profited from the scientific program and the fruitful discussions. We are grateful for having had the opportunity to organize this seminar. Special thanks are due to Carsten Gutwenger and Karsten Klein for their invaluable assistance in the organization and the running of the seminar.