Tata Institute of Fundamental Research
Pseudo-Visibility Graphs
Student Seminar
Speaker:
Bodhayan Roy
Tata Institute of Fundamental Research
School of Technology and Computer Science
Homi Bhabha Road
Date:
Tuesday, 8 Mar 2011 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The notion of visibility graphs can be extended to that of pseudo-visibility graphs, where the edges between vertices do not necessarily remain straight line-segments. We discuss the construction of pseudo-visibility graphs which cannot be drawn on the plane as any valid visibility graph keeping the polygonal boundary unaltered, even though they satisfy all the necessary combinatorial conditions known for a graph to be a visibility graph. This proves that the necessary conditions are not sufficient ones.
| Speaker: | Bodhayan Roy Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha Road |
| Date: | Tuesday, 8 Mar 2011 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The notion of visibility graphs can be extended to that of pseudo-visibility graphs, where the edges between vertices do not necessarily remain straight line-segments. We discuss the construction of pseudo-visibility graphs which cannot be drawn on the plane as any valid visibility graph keeping the polygonal boundary unaltered, even though they satisfy all the necessary combinatorial conditions known for a graph to be a visibility graph. This proves that the necessary conditions are not sufficient ones.