Christoph Brockmann

Implementing an Algorithm for Routing in Unit Disk Graphs

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 18.10.2016


During this thesis a new routing scheme for Unit Disk Graphs described first in Kaplan et al. (2016) was implemented in Python and tested for performance. In addition, dynamic visualisation of the routing process was implemented through Mathplotlib allowing visual inspection of the routing process.
Although experiments show the routing scheme working as intended,  its routing tables scale unfavourably for most graphs that can be feasibly computed in 2016. It is also shown that for the class of random graphs presented in this thesis, routing results are much better than to be expected from the theoretical worst case considerations in the original paper. Finally, this thesis shows that the results given in the original paper can be improved considerably for smaller graphs if 'one-sided' well separated pair decompositions are used as the basis of the global routing tables.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Routing in unit disk graphs.
In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico,
April 11-15, 2016, Proceedings, pages 536–548, 2016.