Parallel computation and graphical visualization of the minimum crossing number of a graph.

摘要

Finding the minimum crossing number of a graph is an interesting and challenging problem in graph theory and applied mathematics. Real world applications of this problem, such as circuit layout and network design, are becoming more and more important.; This thesis presents a parallel algorithm for finding the minimum crossing number of a graph, based on the first sequential algorithm presented in (20). This parallel algorithm was tested on various architectures and a comparison of the corresponding results is given, including running time, efficiency, and speedup. Implementation of the algorithm gives us an ability to verify conjectures proposed for various families of graphs, as well as apply the algorithm to real world applications.; Another important aspect of the problem is ability to draw the solution on the {dollar}2-D{dollar} plane. This thesis gives an overview of graph drawing algorithms, starting with the famous result by Fary, and presents a new algorithm for drawing complete graphs, that uses the output of the previous algorithm.