Finding a plane subgraph with a certain property in ordered bipartite graphs

Abstract

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.