Colloquium Details
Geometric Representations of Graphs
| Author: | Jan Kratochvil Charles University, Prague, CZ |
|---|---|
| Date: | August 29, 2006 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
Geometric representations of graphs keep attracting the attention of researchers and practitioners both as a means of information visualisation and for interesting theoretical properties. For instance, many optimization problems that are computationally hard for general graphs are solvable in polynomial time for various classes of geometric intersection graphs. We will review some classical characterization theorems, hardness results, current development in the area and long standing open problems.
In particular, we will discuss so called interval filament graphs and representations of planar and co-planar graphs.
Biography
Jan Kratochvil is a full professor and head of the Department of Applied Mathematics at Charles University in Prague, Czech Republic. His major area of work is theoretical computer science, in particular algorithms and complexity in graph theory. He received his Ph.D. at Charles University in 1987 for a thesis about domination and codes in graphs. He was the Ph.D. advisor of Daniel Kral who gave his colloquium talk at CIS Department on June 11, 2006.
Jan held a visiting position at the University of Oregon twice in the past (in 1994-95 and in 1999) and keeps coming for short-term visits, since he considers Eugene his second home.