Institute for Algorithms and Complexity (E-11)
Institute for Algorithms and Complexity (E-11)
EN
Place
EN
Place

Implementing a Planar Graph Layout as Webservice

Supervisor: Jens M. Schmidt

Planar graphs are graphs that can be drawn in the plane such that no two edges intersect. There are many algorithms that layout such graph in the plane accordingly. However, open-source implementations that give satisfying and aesthetic results are rare.

In this bachelor thesis, we aim at implementing a well-known planar graph layout algorithm in the already existing webservice grApp (see here). GrApp is already able to visualize and edit graphs smoothly, so that the focus of this work is to implement the algorithm itself. Special attention is given to the aesthetics of the resulting drawing; there are several approaches to improve this (e.g., as in Mathematica). This thesis therefore needs you to have

  • a profound knowledge of JavaScript or C++,
  • skill in writing efficient code for algorithms and the underlying graph data structure,
  • familiarity with graphs, and interest in graph theory and algorithms.

The resulting implementation of this thesis shall be made available open-source and platform-independent within the grApp webservice. If you are interested in this thesis, please contact me by email.

 


 

Betreuer: Jens M. Schmidt

Planare Graphen sind Graphen, die sich ohne Kantenüberkreuzungen in der Ebene zeichnen lassen. Obwohl viele Algorithmen für das Zeichnen von planaren Graphen existieren, sind open-source Implementationen mit brauchbarer ästethischer Ausgabe rar.

In dieser Bachelorarbeit soll ein bereits bekannter Algorithmus zur Zeichnung von planaren Graphen als Teil des bereits bestehenden Webframeworks grApp implementiert werden (siehe hier). GrApp ermöglicht bereits grundlegende und ruckelfreie Visualisierungs- und Editierfunktionen auf Graphen, so der Fokus dieser Arbeit auf die Algorithmenimplementierung selbst gelegt werden kann. Spezielle Aufmerksamkeit soll die Passfähigkeit der Ausgabe erhalten; hier kann sich an den Ausgaben bekannter Software (z.B. Mathematica) orientiert werden. Diese Bachelorarbeit benötigt daher

  • Expertise in JavaScript oder C++,
  • die Fähigkeit, effizienten Code für Algorithmen und die unterliegende Graphendatenstruktur zu schreiben,
  • Kenntnisse von Graphen und Interesse an Graphentheorie und Algorithmen.

Die Ergebnisse dieser Implementierung sollen quelloffen und plattformübergreifend als Teil von grApp zur Verfügung gestellt werden. Bei Interesse an dieser Arbeit kontaktieren Sie mich bitte per Email.