Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25752
Titel: New applications of SPQR-trees in graph drawing
Verfasser: Weiskircher, Rene
Sprache: Englisch
Erscheinungsjahr: 2002
SWD-Schlagwörter: Planarer Graph ; Einbettung <Mathematik> ; Graphenzeichnen ; Orthogonale Darstellung ; SPQR-Baum ; Algorithmus
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: We study two problems that arise in the field of graph drawing. In both problems, we have to optimize a function over the set of all embeddings of a planar graph. The algorithms we have developed to solve the problems rely on the data structure SPQR-tree which represents the set of all embeddings of a planar biconnected graph. The first problem we consider is the problem of inserting an additional edge into a planar graph with the minimum number of crossings. We have found a linear item algorithm to solve this previously unsolved problem to optimality. The second problem is finding an orthogonal drawing of a planar biconnected graph with the minimum number of bends. This problem is knwon to be NP-hard. Using the SPQR-tree, we have developed an integer linear program that is constructed recursively and represents all embeddings of a graph. By combining it with a linear program that describes all orthogonal representations of a graph for a fixed embedding, we have constructed a mixed integer linear program where an optimal solution corresponds to an orthogonal representation with the minimum number of bends over all embeddings of the graph. Solving this program with a commercial mixed integer solver is for large graphs faster than using a previously known branch and bound algorithm for the bend number minimization problem.
Wir untersuchen zwei Probleme auf dem Gebiet des Zeichnens von Graphen. Bei beiden Problemen geht es darum, eine Funktion über der Menge aller Einbettungen eines planaren Graphen zu optimieren. Die Algorithmen, die wir für beide Probleme entwickelt haben, benutzen SPQR-Bäume. Ein solcher Baum repräsentiert die Menge aller Einbettungen eines planaren Graphen. Das erste von uns betrachtete Problem ist das Einfügen einer zusätzlichen Kante in einen planaren Graphen mit möglichst wenigen Kreuzungen. Wir haben einen Algorithmus mit linearer Laufzeit entwickelt, der dieses Problem optimal löst. Das zweite Problem ist das Berechnen einer orthogonalen Zeichnung mit der minimalen Anzahl von Knicken für einen planaren zweizusammenhängenden Graphen. Es ist bekannt, dass dieses Problem NP-schwer ist. Wir benutzen den SPQR-Baum, um ein ganzzahliges lineares Programm zu entwickeln. Dieses wird rekursiv berechnet und seine Lösungen entsprechen den Einbettungen des Graphen. Dieses ganzzahlige lineare Programm haben wir mit einem linearen Programm kombiniert, bei dem eine optimale Lösung einer orthogonalen Repräsentation des Graphen mit der minimalen Knickanzahl für eine feste Einbettung entspricht. Das Resultat ist ein gemischt-ganzzahliges lineares Programm, bei dem eine optimale Lösung einer orthogonalen Repräsentation des Graphen entspricht, die knickminimal über alle möglichen Einbettungen des Graphen ist. Wir lösen dieses Programm mittels eines kommerziellen Lösers für gemischt-ganzzahlige Programme. Unsere Experimente zeigen, dass dieses Vorgehen für grosse Graphen schneller zum Ziel führt als das Lösen des selben Problems mit Hilfe eines bekannten Branch & Bound Algorithmus.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-2441
hdl:20.500.11880/25808
http://dx.doi.org/10.22028/D291-25752
Erstgutachter: Harald Ganzinger
Tag der mündlichen Prüfung: 23-Mai-2002
SciDok-Publikation: 17-Mai-2004
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
ReneWeiskircher_ProfDrPetraMutzel.pdf2,07 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.