This thesis introduces a new graph-an ordered bipartite graph and considers several problems on the ordered bipartite graph. An ordered bipartite graph is defined as a bipartite graph which has a specific geometric property such that the edges connecting two vertices are line segments, and the vertices are lying on two parallel lines and the vertices on each parallel line are ordered. This thesis presents simple and efficient algorithms for the problems to find certain subgraphs, of a given ordered bipartite graph, which satisfy a specified property and of which no two edges intersect each other.
Using the algorithm for finding a maximum independent set of a permutation graph, O(|E(G)|log|V(G)|) algorithms for the minimum plane tree cover and the maximum plane matching problems were presented, where |E(G)| and |V (G)| are the cardinalities of the edge set and the vertex set, respectively. For the minimum plane spanning tree, the longest plane path, and the plane Steiner tree problems, linear time algorithms were developed by using the dynamic programming. The minimum plane tree cover and the minimum plane spanning tree problems have the applications in PCB routing and the maximum plane matching problem in VLSI routing.
순서화된 이분그래프(ordered bipartite graph)는 정점들이 두개의 평행선상에 있고 각 선상의 정점끼리 순서가 정해진 이분그래프이다. 본 논문에서는 주어진 순서화된 이분그래프에 대해 특정한 성질을 만족하면서 서로 교차하는 에지를 갖지 않는 부그래프를 찾는 문제들을 고려하였다. 최소 plane tree cover와 최대 plane matching 문제에 대해서는 O(| E(G)|log|V(G)| 알고리즘을 제안하였고 최소 plane spanning tree, 최장 plane path, plane Steiner tree 문제들에 대해서는 각각 선형시간의 알고리즘을 제안하였다.
