Colloquium Details
Extending Partial Geometric Representations of Graphs
| Author: | Professor Jan Kratochvil Charles University, Prague, Czech Republic |
|---|---|
| Date: | October 10, 2014 |
| Time: | 14:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
Geometric representations of graphs are popular and well studied for their practical motivation and interesting structural and algorithmic properties. Many of intersection defined classes of graphs (such as interval graphs, circle graphs, permutation graphs) can be recognized in polynomial time, their intersection representations can be constructed efficiently, and many optimization problems NP-hard in general can be solved in polynomial time on these graph classes.
Only recently a natural question of extending partial representations has been considered. This question falls into the paradigm of completing a partial solution, whose instances are often provably more difficult than constructing a solution without being given initial constraints. Such examples are well known for instance in the area of graph coloring problems. Architects describe this phenomenon by saying that "Building from scratch is easier and cheaper than reconstructing an old house".
In the talk we will survey existing complexity results about extending partial representations of interval, proper interval, unit interval, circle, permutation, and function graphs. To our surprise in all of these cases the partial representation extension problem remains polynomially solvable. On the contrary, extending partial contact representations of planar graphs becomes NP-complete.
Biography
Jan Kratochvil received his Ph.D. in Mathematics at Charles University in Prague, Czechoslovakia, in 1987, under the supervision of Jarik Nesetril. He is a professor of theoretical computer science at the same university, now in the Czech Republic. In 2002 - 2010 he was the president of the Czech Mathematical Society. Since 2012 he is the dean of the Faculty of Mathematics and Physics at Charles University.
In 1994 Professor Kratochvil visited the CIS department as a Fulbright fellow, and later in 1999 and 2002 as a visiting associate professor. He and his current and former students still maintain strong links to and collaboration with the department.