Algorithms and drawings for Mixed linear layouts of graphs

Abstract

Ein gemischtes lineares Layout eines Graphen ist eine totale Ordnung seiner Knoten, so dass die Kanten als Elemente betrachtet werden können, die in dieser Reihenfolge mit den beiden Datenstrukturen eines Stapelspeichers und einer Warteschlange verarbeitet werden können. Layouts, die nur Stapelspeicher verwenden, werden als Bucheinbettungen bezeichnet, was ein weit erforschtes Thema ist und auch reine Warteschlangenlayouts finden viel Beachtung. Die Kombination dieser beiden Konzepte zur gleichen Zeit wird jedoch seltener verwendet. Die Literatur beschreibt viele Algorithmen, Eigenschaften und Ergebnisse für Layouts, die entweder aus Stapelspeichern oder Warteschlangen bestehen, aber oft fehlen die passenden Gegenstücke für gemischte Layouts. In dieser Diplomarbeit stellen wir neue Ergebnisse in den Bereichen Komplexität, Heuristiken und Zeichnungen für gemischte Layouts vor, die es vorher noch nicht gegeben hat oder die bestehende übertreffen. Um dies zu erreichen, haben wir zum einen bereits bestehende Methoden für reine Layouts wiederverwendet und zum anderen neue Ideen zur Lösung der Probleme eingeführt. Wir erwarten, dass diese Ergebnisse dazu beitragen werden gemischte lineare Layouts besser zu verstehen und es ermöglichen, diese für praktische Zwecke zu nutzen.

A mixed linear layout of a graph is a total order of its vertices in a way that the edges can be seen as elements that are processed in this order with a stack and a queue data structure. Layouts that only use stacks are known as book embeddings and is a widely researched topic. Queue layouts also receive much attention. However, the study of these two concepts in combination is less understood. The literature describes many algorithms, properties and results for layouts that consist of either stacks or queues but the adequate counterparts for mixed layouts are often missing. In this thesis, we introduce new results for computational hardness, heuristics and drawings for mixed linear layouts that have not existed before or outperform existing ones. To achieve this, we reused existing methods of linear layouts as well as introduced new ideas to tackle the problems. We expect that these results will help to understand mixed linear layouts better and use them for practical purposes.