Carleton University - School of Computer Science Honours Project
Winter 2021
An efficient implementation of a fast algorithm that solves the product structure of planar graphs
ABSTRACT
The problem of finding the product structure of planar graphs can be solved in a runtime of O(n logn) using the modified algorithm published by Morin [Morin, 2020a]. This version of the algorithm has already been implemented in Python as a proof of concept and shows a significant improvement in runtime compared to similar algorithms. The next step in demonstrating the use of this algorithm is to create an implementation in C++ that is more efficient than the Python implementation. The two major goals of making this C++ implementation are to execute the algorithm successfully and then to significantly outperform the Python implementation. The C++ implementation that was created met both of these goals. This C++ implementation’s correctness was verified through a rigorous testing process, and was then tested for performance against the Python implementation. In these test cases, the C++ implementation executed the algorithm approximately 20 times faster, on average, than the Python implementation and produced less than 1/3 of the amount of output.