Events & News
Colloquium
| Category | Lecture |
| Date | Thursday, April 10, 2014 |
| Time | 11:00 am |
| Concludes | 12:00 pm |
| Location | Gould-Simpson 906 |
| Details | Please join us for coffee and light refreshments at 10:45am in the 9th Floor Atrium. Faculty Host: Stephen Kobourov |
| Speaker | Michael Kaufmann |
| Title | Professor |
| Affiliation | University of Tubingen, Germany |
On Slanted Orthogonal Graph Drawing
We introduce a new graph drawing model that we call slanted orthogonal graph drawing. While in traditional orthogonal drawings each edge is made of axis-aligned line-segments, in slanted orthogonal drawings intermediate diagonal segments on the edges are also permitted, which allows for: (a) smoother bends in the drawing (as they are replaced by pairs of “half-bends”), and, (b) emphasizing the crossings of the drawing (as they always appear at the intersection of two diagonal segments). We discuss an approach to achieve bend-optimal slanted orthogonal representations, and an LP formulation to compute a slanted orthogonal drawing. Unfortunately, bend-optimal slanted orthogonal drawings may require exponential area. Therefore we give an efficient heuristic to compute close-to-optimal drawings in terms of the total number of bends using quadratic area. Finally we discuss related open questions and future work.
Biography
Prof. Michael Kaufmann works on graph theory, efficient algorithms, combinatorics and discrete mathematics, information visualization, schematics, diverse applied topics from software engineering, to parallel computation and bioinformatics. He has worked as a professor at the University of Tubingen in Germany since 1993. He is an editor of the Journal of Graph Algorithms and Applications and the Journal of Discrete Algorithms and has been program committee chair for the European Symposium on Algorithms (ESA), Symposium on Graph Drawing (GD), and the Workshop on Graph-Theoretic Concepts in Computer Science (WG). He is also a co-founder of the visualization company yWorks.