A rectangular dual of a graph G is a dissection of a polygon into rectangles for which G describes the adjacency relations among the rectangles. So far there have been lots of researches on the rectangular duals of which bounding polygons are rectangles. This thesis considers the rectangular duals of which bounding polygons are not restricted to rectangles. First we deal with the rectangular duals whose bounding polygons are convex rectilinear polygons. The number and relative positions of vertices are used in classifying convex rectilinear polygons. We present the characterization of graphs having rectangular duals with each type convex rectilinear bounding polygons. Second the class of graphs having rectangular duals with arbitrary rectilinear bounding polygons is shown. These results can be utilized in the floorplanning process of many engineering problems.
그래프 G의 rectangular dual은 인접관계가 G로 표현되는 직사각형들로 다각형을 분할한 것이다. 지금까지 rectangular dual에 대하여 많은 연구가 있었는데, 이들은 대부분 경계다각형이 직사각형인 경우를 다루었다. 본 논문에서는 경계다각형이 직사각형에 국한되지 않은 rectangular dual을 다루었다. 첫째로 경계다각형이 볼록직교다각형인 rectangular dual들을 고려하였다. 볼록직교다각형들을 꼭지점의 갯수와 상대적인 위치를 이용하여 분류하였다. 볼록직교다각형의 각 유형에 대하여, 경계다각형이 그 유형에 속하는 rectangular dual이 존재하는 그래프의 특성을 제시하였다. 둘째로 경계다각형이 임의의 직교다각형인 rectangular dual이 존재하는 그래프의 특성을 제시하였다. 여러가지 실제적인 문제에서 필요한 floorplanning에 이 결과들을 이용할 수 있다.
