Efficient drawing of orthogonal networks for data flow diagrams
Motivation: Network drawing is concerned with the development of methods for automatically drawing graphs in order to highlight important features of such networks and to produce aesthetically pleasing visualisations. For example, if the network can be drawn without crossing, then it is desirable to generate such a drawing in which no two edges cross, and if the edges in the drawing bend strongly, the optimisation objective is bend minimisation.
This bachelor or master thesis is about orthogonal drawings in which edges are represented by horizontal and vertical segments. Such drawings are often used in applications such as database systems (E-R diagrams) and software engineering (data flow diagrams), as well as circuit design (schematics). In such applications, one tries to minimise the number of bends in the drawings in order to keep the complexity low for the viewer.
Methods: In the paper “Computing Orthogonal Drawings in a Variable Embedding Setting” (https://link.springer.com/chapter/10.1007%2F3-540-49381-6_10) a method is presented to find orthogonal drawings with the smallest number of bends. The runtime of the procedure is efficient in the size of the network and depends exponentially only on the number of nodes with degree at least 4.
Project goals and work packages:
- Work through the paper “Computing Orthogonal Drawings in a Variable Embedding Setting” (10 pages) and work out the missing intermediate steps.
- Correctness and runtime analysis of the procedure
- Investigate the process for possible runtime improvements using modern techniques such as efficient data reduction rules and balanced planar separators.
- Extensive tests and documentation of experimental results of the found data reductions with regard to the computational and storage effort compared to experiments in the article.
