Planaaristen verkkojen piirtäminen hajautetusti CONGEST-mallissa
Hannes Sederholm · Aaltodoc (Aalto University) · 2022
The concept of planarity has been widely studied in many contexts. However, in the distributed setting and specifically in the CONGEST model, relatively little work has been done in the area. Especially, the problem of drawing planar graphs has not been solved previously in CONGEST. In this thesis the problem is studied by inspecting existing non-distributed algorithms. As a result a novel CONGEST algorithm solving this problem is presented. The algorithm utilizes an existing distributed algorithm to obtain a combinatorial embedding of a graph. Given the running time of obtaining an embedding the running time of the algorithm is negligible, and thus analysis of the performance of the algorithm focuses on the quality of the drawings. The quality of the drawings are evaluated with examples created by programmatically simulating the execution of the algorithm.