| Though graph theory has a long history of research, mostly it has concentrated on theoretical foundations. However, for the last two decades, the research in algorithmic graph theory and applications have grown substantially. Some special classes of graphs and certain graph problems have received more attention largely due to applicability to real world problems and intractability of NP-complete problems in graphs in general. This research is four-fold (a) to solve polynomial time problems (maximum matching) and NP-complete problems (disjoint paths); (b) to improve the current best known results and to provide solutions to selected unsolved problems; (c) to provide sequential and parallel algorithms; and (d) to present theoretical and experimental results. In this study, I present solutions to (a) disjoint paths algorithms on cographs; (b) parallel matching on bipartite permutation graphs; (c) disjoint paths on interval graphs; and (d) listing nearly planar graphs. |
