Title: Algorithms and drawings for Mixed linear layouts of graphs
Language: English
Authors: Col, Philipp <<de>> 
Qualification level: Diploma
Keywords: mixed linear layout; stack page; queue page
Advisor: Nöllenburg, Martin  
Assisting Advisor: Klute, Fabian 
Issue Date: 2019
Number of Pages: 75
Qualification level: Diploma
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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-125562
http://hdl.handle.net/20.500.12708/13807
Library ID: AC15381170
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

15
checked on Feb 24, 2021

Download(s)

33
checked on Feb 24, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.