Events & News
Colloquium
| Category | Lecture |
| Date | Thursday, February 24, 2011 |
| Time | 11:00 am |
| Location | Gould-Simpson 906 |
| Details | Light refreshments in 9th floor atrium area - 10:50 a.m. |
| Speaker | Deniz Sarioz |
| Affiliation | CUNY Graduate School and University Center |
Bounds and Algorithms regarding Obstacle Representations of Graphs
Abstract: Given a graph G, an "obstacle representation" of G is a set of points in the plane representing the vertices of G together with some polygonal obstacles such that the edges in G correspond to pairs of points that can see each other. This notion is motivated by wireless sensor networks and line-of-sight networks. The "obstacle number" of G is the minimum number of obstacles in an obstacle representation of G.
Alpert, Koch and Laison gave these definitions in a DCG paper of December 2009 and showed a sequence of graphs with obstacle number at least some constant times the square root of log n.
In the first half of this talk, I will outline how (in joint work with Janos Pach) I used extremal graph theoretic tools to show that the number of (unlabeled) graphs with bounded obstacle number is at most 2^o(n2).
In the second half of this talk, we will explore the question of computing a minimum obstacle representation for a fixed graph drawing. I will cast this as an instance of the well-studied set cover problem, allowing us to efficiently compute a representation with O(c_opt log n) obstacles where c_opt is the number of obstacles required. By a result that I recently obtained, this is superseded by an efficient algorithm that guarantees based on epsilon-net theory a representation with O(c_opt log c_opt) obstacles.