Campus Event Calendar
Event Entry
New for: D2, D3
What and Who
PhD Application Talk: On Fully Characterizing Terrain Visibility Graphs
Noushin Saeedi
PhD Application Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 14 October 2011
11:15
90 Minutes
E1 4
024
Saarbrücken
Abstract
A terrain is an x-monotone polygonal line in the xy-plane. Two vertices of a terrain are mutually visible if the line segment that connects them lies above the terrain (except at its endpoints). A graph whose vertices represent terrain vertices and whose edges represent mutually visible pairs of terrain vertices is called a terrain visibility graph. Understanding the graph theoretic properties of all terrain visibility graphs may help us understand the combinatorial structure of these geometric objects and help to address problems related to geometric visibility. The properties that are true of all terrain visibility graphs are called necessary properties. The set of properties that, if true, imply that a graph is a terrain visibility graph is called a sufficient set. We would like to find properties that are both necessary and sufficient; that is, we would like to characterize, graph theoretically, terrain visibility graphs. Abello et al. [Discrete and Computational Geometry,14(3):331-358,1995] studied an equivalent class of visibility graphs and claimed to have solved the characterization problem in a series of two papers, only one of which has appeared in the literature. They approached the problem of whether certain graph properties are sufficient by deriving the slope order requirements for the lines that connect all pairs of terrain vertices, using combinatorial properties of terrain visibility graphs. The main contribution of our work is to give a much simpler proof for the sufficiency of these properties for obtaining such a slope ordering. Our approach attempts to clarify the implications of the graph theoretic properties on the ordering of the slopes, and may be interpreted as defining properties on an underlying oriented matroid.
Contact
IMPRS-CS
-1803
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Please note: The talks will take place in random order!
Heike Przybyl, 10/11/2011 15:58 -- Created document.