Combinatorial and Geometric Aspects of Computational Network Construction [Elektronische Ressource] : Algorithms and Complexity / Marcus Krug. Betreuer: D. Wagner

Combinatorial and Geometric Aspects ofComputational Network ConstructionAlgorithms and Complexityzur Erlangung des akademischen Grades einesDoktors der Naturwissenschaftenvon der Fakultät für Informatikdes Karlsruher Instituts für Technologie (KIT)genehmigteDissertationvonMarcus Krugaus ErfurtTag der mündlichen Prüfung: 21. Dezember 2011Erster Gutachter: Frau Prof. Dr. Dorothea WagnerZweiter Gutachter: Herr Prof. Dr. Michael KaufmannAcknowledgmentsFirst of all I would like to thank Dorothea Wagner for the opportunity to work in an interestingand multifaceted field of computer science and for the freedom to choose which problemsto work on. When I was a student, her lecture on theoretical computer science fascinatedand inspired me and has changed my view on the field. I would also like to thank MichaelKaufmann for accepting to review my thesis despite the fact that he was already reviewingtwo other theses at the time.I am grateful to all members of Dorothea Wagner’s group for the friendly, stimulating andproductive atmosphere they provided. Working in Dorothea Wagner’s group was a greatexperience and I always enjoyed my time in the office. I owe special thanks to ReinhardBauer and Ignaz Rutter for proof-reading large portions of my thesis and for the fun wehad during work. Additionally, I would like to thank Reinhard for his friendship and hisgood-humored nature that would always lift my spirit.