Neue Anwendungen von SPQR-Bäumen im Graphenzeichnen

"New Applications of SPQR-Trees in Graph Drawing"

Es werden zwei Probleme auf dem Gebiet des Zeichnens von Graphen
untersucht. Bei beiden Problemen geht es darum, eine Funktion über Menge
aller Einbettungen eines planaren Graphen zu optimieren. Die
Algorithmen, die für beide Probleme entwickelt wurden, benutzen
SPQR-Bäume. Das erste betrachtete Problem ist das Einfügen einer
zusätzlichen Kante in einen planaren Graphen mit möglichst wenigen
Kreuzungen. Es wurde ein 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. Es wurde ein gemischt-ganzzahliges
lineares Programm entwickelt, das unter Benutzung des SPQR-Baums
berechnet wird, und bei dem optimale Lösungen orthogonalen
Repräsentationen des Graphen mit der minimalen Anzahl von Knicken
entsprechen. Die Experimente zeigen, dass das Lösen dieses
gemischt-ganzzahligen Programmes für große Graphen schneller zum Ziel
führt als das Lösen desselben Problems mit Hilfe eines bekannten Branch
& Bound Algorithmus.



Professor Dr. Ph. SLUSALLEK
Dekan der NTF I