| 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.