Visibility properties of graphs and their recognition

Abstract

The subject of this study is principally visibility graphs. The visibility graph characterization problem is to find necessary and sufficient conditions for a graph to be the visibility graph of a simple polygon. In a broad sense, this problem is to identify geometric properties (visibility in this study) hidden behind a combinatorial structure (a graph in this study), which is not only fundamental by itself but also useful to dealing with a non-geometric problem geometrically. Although the visibility graph characterization problem is fundamental, no complete characterization has been available, yet. This thesis presents new results on the problem in three directions. First, the polygon class is restricted to funnels notable for their fundamental role in visibility algorithms. The visibility graph of a funnel called an F-graph is characterized in two ways: one to presents its basic visibility nature and the other to provide an efficient recognition algorithm. An optimal recognition algorithm is also given using the second characterization. When the algorithm recognizes a graph to be an F-graph, it also reports one of the Hamiltonian cycles defining the boundary of a corresponding funnel. A proof is also offered that an F-graph is weakly triangultated and therefore perfect. Second, a new characterization of a connected proper interval graph is presented in terms of visibility. A 2-connected proper interval graph is first characterized as the visibility graph of a spiral polygon of special type, and then the result is generalized to a connected proper interval graph. For the generalization, the notion of a series of polygons is proposed to deal with a graph having a cut vertex. This characterization shows that the notion of visibility is embedded in preference/indifference relations. From the reverse view, these results are also the characterizations of. the visibility graph of a spiral polygon of special type. Third, k-trees and k-paths are consider...