Colloquium Details
On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
| Author: | Jan Kratochvil Charles University, Prague |
|---|---|
| Date: | August 31, 2010 |
| Time: | 16:00 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
Some graphs admit drawings in the Euclidean $k$-space in such a (natural) way, that edges are represented as line segments of unit length. Such embeddings are called k-dimensional unit distance representations. The embedding is strict if the distances of points representing nonadjacent pairs of vertices are different than 1. When two non-adjacent vertices are drawn in the same point, we say that the representation is degenerate. Computational complexity of nondegenerate embeddings has been studied before. We initiate the study of the computational complexity of (possibly) degenerate embeddings. In particular we prove that for every k>1, deciding if an input graph has a (possibly) degenerate k-dimensional unit distance representation is NP-hard.
The talk is based on a joint work with B. Horvat and T. Pisanski that was presented at IWOCA 2010.
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.