McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome!

DATE: Wednesday, October 4th
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: Graph isomorphisms in graph drawing
SPEAKER: Franz J. Branenburg, University of Passau, Germany

What is a nice or aesthetically pleasing drawing of a graph? This problem is formally expressed in terms of cost measures such as area or edge length or a uniform distribution of the nodes. Empirical test have revealed that symmetries in drawings are important, when the intended meaning of a graph is of our concern.

In graph theoretic terms symmetry is expressed by isomorphisms. Here the largest common subgraph problem is most appropriate. It focusses on disjoint isomorphic subgraphs and is similar, but essentially different from the well-known subgraph isomorphism problem. This new problem is NP-complete, even for planar and outerplanar graphs. However, there is an elegant soluton for trees.

We'll study various common graph drawing algorithms and their properties concerning graph isomorphisms and symmetries. It turns out that only some respect isomorphisms and support symmetries.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at