Distributed Drawing of Planar Graphs in the CONGEST model

Thumbnail Image

Files

master_Sederholm_Hannes_2022.pdf (533.52 KB)

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2022-07-29

Department

Major/Subject

Computer Science

Mcode

SCI3042

Degree programme

Master’s Programme in Computer, Communication and Information Sciences

Language

en

Pages

34

Series

Abstract

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.

Verkkojen planaarisuutta on tutkittu laajasti monesta eri näkökulmasta. Hajautettujen verkkojen yhdeydessä, ja erityisesti CONGEST-mallissa, sitä ei kuitenkaan ole tutkittu kovin kattavasti. Erityisesti planaaristen verkkojen piirtämiseen ei ole ollut toimivaa ratkaisua CONGEST-mallissa. Tässä työssä ongelmaa lähestytään tarkastelemalla olemessa olevia ei hajautettuja algoritmeja. Tuloksena esitellään CONGEST algoritmi, joka ratkaisee ongelman. Algoritmi hyödyntää olemassa olevaa hajautettua algoritmia, joka määrittää jokaiselle verkon solmulle planaarista piirrustusta vastaavan järjestyksen. Verrattuna järjestyksen etsimiseen piirtämisalgoritmin ajoaika on pieni. Tästä syystä algoritmin analyysissä keskitytään tuloksena saatavien piirrustusten laatuun. Laatua arvioidaan algortmia ohjelmallisesti simuloimalla tuotettujen esimerkkien kautta.

Description

Supervisor

Uitto, Jara

Thesis advisor

Latypov, Rustam

Keywords

distributed algorithms, CONGEST model, planarity, graph drawing, planar embedding

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202208285084

Collections

[dipl] Perustieteiden korkeakoulu / SCI