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 considered. They are generalization of ordinary trees and paths, respectively, special types of chordal graphs like interval graphs, and perfect. The first main result shows that a 3-path is a visibility graph. An extremal problem which concerns the visibility graphs with minimum number of edges is also proposed. As a result, k-connected extremal visibility graphs are characterized as a subclass of k-trees when k = 2 or 3.
본 논문에서는 임의의 그래프가 다각형의 가시그래프가 되기 위한 필요 충분조건을 찾는 문제에 대한 연구를 수행하였다. 이 문제는 크게 보면 그래프라는 조합론적 구조에서 가시성이라는 기하학적인 성질을 규명하는 작업이라 할 수 있다. 그러나 이 문제는 아직까지 해결되지 않고 있는 문제로서, 본 논문에서는 이 문제에 대한 새로운 결과를 제시하였다.
먼저 많은 가시 알고리즘에서 사용되고 있는 구조인 funnel 다각형으로 다각형의 부류를 제한하여 두 가지 필요 충분 조건을 제시하였다. 첫번째 것은 funnel 다각형의 가시그래프의 근본적인 특성을 잘 보여주고 있으며, 두번째 것은 인식 알고리즘에 유리하다. 두번째 필요 충분 조건을 이용하여 funnel 다각형의 가시그래프를 인식하는 최적 알고리즘을 제시하였고 funnel 다각형의 가시그래프가 perfect 그래프임을 증명하였다.
다음으로 가시그래프의 입장에서 proper interval 그래프의 새로운 필요 충분 조건을 제시하였다. 먼저 연결도가 2 이상인 proper interval 그래프와 제한된 모양의 spiral 다각형의 가시그래프가 같은 부류임을 밝혔고 이를 연결된 proper interval 그래프인 경우로 확장하였다. 이를 위해 다각형 series라는 새로운 개념을 도입하였고 그 결과로부터 preference/indifference relation이 가시성 개념을 함축하고 있다는 것을 밝혔다.
마지막으로 k-tree와 k-path를 고려하였다. 이들 그래프 부류는 트리와 경로의 일반화된 형태이며 chordal 그래프의 특별한 형태이고 또한 perfect 그래프임이 알려져 있다. 먼저 모든 3-path는 가시그래프임을 증명하였다. 또한 최소 갯수의 예지를 가지는 가시그래프의 필요 충분 조건을 찾는 문제를 제안하였으며 그에 대한 결과로서 k =2 혹은 3일 경우 연결도가 k 이상인 최소 가시그래프와 k-tree는 같은 부류임을 증명하였다.
