International Symposium on Graph Drawing 2010
Graph Drawing is concerned with the geometric representation of graphs and networks and is motivated by those applications where it is crucial to visualize structural information as graphs.
Since graph drawing methods form the algorithmic core of network visualization, bridging the gap between theoretical advances and implemented solutions is an important aspect.
The International Symposium on Graph Drawing is the main annual event in this area. Researchers and practitioners working on any aspect of graph drawing are invited to contribute and participate.
In 2010, the conference was held on the campus of the University of Konstanz.
18th International Symposium on Graph Drawing
Dr. Clemens Dirscherl
Carsten Thomassen (Technical University of Denmark) - Graph Decomposition
Abstract
János Barát and I made the following conjecture: For every tree T, there is a natural number kT such that every kT-edge-connected graph of size divisible by |E(T)| has an edge- decomposition into subgraphs each isomorphic to T. The conjecture is trivial when T has at most two edges. When we made the conjecture we could not prove it for one single tree with three or more edges. However, we showed that the conjecture holds for the claw (the star with three edges) provided Tutte's 3-flow conjecture is true. In fact, when restricted to the claw, our conjecture is equivalent to the weakening of Tutte's 3-flow conjecture, suggested by Jaeger, that every graph of sufficiently high (but fixed) edge-connectivity has an orientation such that each vertex has the same indegree and outdegree when these numbers are reduced modulo 3.
A few years ago, I verified the conjecture for the path with four edges, and later for the path with three edges. I have now verified the conjecture for an infinite family of trees.
Bio sketch
Carsten Thomassen has been Professor of Mathematics at the Technical University of Denmark since 1981. He is editor-in-chief of the Journal of Graph Theory and of the Electronic Journal of Combinatorics, and he is on the editorial boards of Discrete Mathematics, Journal of Combinatorial Theory Ser. B, Combinatorica, and the European Journal of Combinatorics. He is a member of the Royal Danish Academy of Sciences and Letters.
Video
Stream (700 kbps)
Stream (250 kbps)
Peter Eades (University of Sydney) - On the Future of Graph Drawing
Bio sketch
Peter Eades is Professor of Software Technologies at the University of Sydney. His PhD work was in Combinatorial Mathematics. His interest in graph visualization began with some consulting contracts in the early 1980s. Since then most of his research has been inspired by problems in Graph Visualization (despite some brief flirtations with Data Structures, Software Engineering, and Human User Interfaces).
Videos
Stream (700 kbps)
Stream (250 kbps)