This project is concerned with the design of efficient parallel algorithms for solving various graph problems arising from disparate areas in Computer Science. These problems can be roughly divided into three categories: graph layout problems, some fundamental problems for planar graphs, and optimization problems for a class of special graphs including permutation graphs, comparability graphs, and cographs. Because of their broad applications in a variety of applied science disciplines, sequential algorithms for these problems have been extensively studied. But it appears difficult to solve them in parallel. Either no fast parallel algorithms for solving them are known; or parallel algorithms exist, but require a very large number of processors. The properties of these graphs and intrinsic structures of these problems will be investigated, and new parallel algorithms for solving them will be developed (or the efficiency of existing parallel algorithms will be improved). A main concern of this project is to identify common characteristics and to find algorithmic tools for the problems in each category. The results produced from this study will provide not only efficient parallel algorithms for individual problems, but also new understanding of these special graphs and new techniques for designing parallel algorithms.
