Open Collections

On fully characterizing terrain visibility graphs

University of British Columbia

A terrain is an x-monotone polygonal line in the xy-plane. Two vertices of a terrain are mutually visible if and only if they are adjacent or 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 the core induced subgraphs of the visibility graphs of staircase polygons, which are exactly the class of terrain visibility graphs. They showed that the visibility between vertices in such structures implies some ordering requirements on the slopes of the lines that connect pairs of vertices in any realization. They approached the problem of whether certain graph properties are sufficient by creating a slope order on the lines that connect all pairs of polygon vertices (in a possible realization) such that the slope order is consistent with the desired visibility graph. The main contribution of our work is to give a much simpler proof that these properties guarantee such a slope ordering. Our proof consequently gives a faster algorithm for constructing this slope order. 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.

Text

2012-03-30

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/41902

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/