Parallel graph drawing

I proposed a meta-algorithm for graph drawing in a parallel computing environment. Specifically, I proposed a parallel communication scheme which takes in three algorithms

1. A graph partitioning algorithm
2. A graph drawing algorithm
3. A repositioning algorithm and combines these things to draw graphs in a distributed memory parallel system.

The high-level approach is to first partition the graph so that each processor gets a subgraph which it will draw using the graph drawing algorithm. One processor then computes a high-level layout for each of the subgraphs by contracting each subgraph into a supernode and then running the graph drawing algorithm on the graph of supernodes. Then, each processor is relayed its corresponding supernode position which allows each processor to reposition its nodes to match the relative position in the graph of supernodes. Finally, a repositioning algorithm is run to ensure that each none of the individual graph drawings overlap, and the graph drawings are aggregated on a root processor.

I implemented this program in C++, using MPI, OGDF, and METIS.

As of now, I have tested this on a few graphs to obtain timing results. There is a small document summarizing my results using METIS to partition, \(\Theta(n \log n)\) spring-embedders, and a simple greedy repositioning algorithm.