# "Drawing Graphs within Graphs"

## Introduction

The tenth annual graph-drawing contest will be held in conjunction with 11th International Symposium on Graph Drawing 2003.

By the experience from the previous contests, we have revised the concept for this year. We wish to address more participants, and hope that the theme will attract both young and experienced researchers, and other participants from within and outside the graph drawing community.

Rather than asking for "nice" drawings of certain challenge graphs and awarding the best drawings in each category, we set a theme for the contest which can be addressed in various ways. Furthermore, we give authors more room for a presentation of their work. The authors of accepted/awarded submissions will be recommended for an invitation to submit their contribution in a special section of the special issue of the Journal of Graph Algorithms and Applications devoted to Graph Drawing 2003. Besides, the Report on the Graph Drawing Contest in the Proceedings of GD2003 will summarize all accepted/awarded submissions. Finally, the winning entry is awarded a prize fund of EUR 1,000.

Reports on previous contests can be found in the proceedings of the Symposium on Graph Drawing, published in the Springer Lecture Notes in Computer Science.

## Theme for 2003

The theme of this year's contest is "drawing graphs within graphs".

It emphasizes the largely open question of how to visualize distinguised graph structures that are contained in larger graphs in a distinct way. While any question related to this general theme may be addressed, we give some examples to spark your creativity:

• Given a distinguished subgraph (structurally or extrinsically defined). Produce a drawing that makes the structure of the subgraph apparent and well visible (for example a provider's subnet in a telecommuncation network). Show the existence of such a subgraph and display it by a graph drawing algorithm. (for example a (or all) K{3,3} or K5 in a non-planar graph). Modify a drawing of the subgraph minimally to accomodate the rest (as in an evolving sequence of graphs).
• Given a (partial) drawing of a graph, embed the distinguished subgraph into the drawing in a suitable way.
• Given a large graph, make all occurrences of a set of small graphs visible. Show how they are distributed over the graph, or how they relate to each other.
• Make isomorphic subgraphs recognizable.
• Given a nested graph, place contained graphs in a layout of their containers or vice versa.
• Draw a graph using templates for certain subgraphs.

## Contest Data

Two real-world data sets are provided that can be used to illustrate your results towards the theme. (The files provide additional information about the graphs; note that you may also use your own data).

1. A biological network representing the transcriptional regulation of Escherichia coli, in which recurring motifs (small isomorphic subgraphs) are of interest (courtesy of Uri Alon, The Weizmann Institute).
ascii - File description
GraphML
GML
LEDA - File description
2. A social network representing informal communication among organizations involved in drug policy making, in which the edge-induced subgraph of confirmed relations is of interest (courtesy of Patrick Kenis, Tilburg University).
ascii - File description
GraphML
GML
LEDA - File description

## Call for contributions

Contributions are solicited that address the theme "graphs within graphs" from a graph drawing point of view.

We particularly encourage young researchers to start working on the topic and take the chance of publishing first results or novel, but potentiallynot fully developed, ideas in a respected journal.

Submissions may contain visualizations, drafts, case studies, concepts, algorithms, experiments, structural results, etc., and may be in the form of textual descriptions (no more than 6 pages), drawings, videos, implementations, or other content. The only set requirement is that they must contain visualizations related to the theme (at least one drawing/picture).

Submissions should be sent (preferably in electronic form in .ps, pdf,) to

brandenb@informatik.uni-passau.de (Franz J. Brandenburg, University of Passau, 94030 Passau, Germany)

and must be received by August 15, 2003. They will be reviewed by a panel of experts on the basis of their originality, novelty, creativity, and soundness.

Accepted submissions as well as a special award for the most outstanding contribution will be announced during the GD 2003 conference dinner, and shall be published on the conference web pages soon after.

## Awards

The accepted submissions will be recommended by the jury for invitation as short submissions to the GD 2003 special issue of JGAA.

The best contribution is awarded with a prize money of EURO 1000.

## Contest Jury

The following experts will evaluate submissions and decide on which submissions are considered for a short publication in the Journal of Graph Algorithms and Applications and on the best contribution.

• Franz J. Brandenburg (Passau)
• Ulrik Brandes (Passau)
• Peter Eades (Sydney)
• Joe Marks (MERL, Cambridge)

## Sponsors

AT&T Research
MERL - Mitsubishi Research Lab

## Contact

Prof. Dr. Franz J. Brandenburg
brandenb@informatik.uni-passau.de