School of Technology and Computer Science Seminars
Pseudo-Visibility Graphs
by Mr. Bodhayan Roy (School of Technology and Computer Science)
Tuesday, March 8, 2011
from
to
(Asia/Kolkata)
at Colaba Campus ( A-212 )
at Colaba Campus ( A-212 )
Description |
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. |
Organised by | John Barretto |