Neue Anwendungen von SPQR-Bäumen im Graphenzeichnen

Abstract

Wir untersuchen zwei Probleme auf dem Gebiet des Zeichnens von Gra- phen. Bei beiden Problemen geht es darum, eine Funktion über der Menge aller Einbettungen eines planaren Graphen zu optimieren und wir verwenden jeweils SPQR- Bäume um die Probleme zu lösen. Das erste von uns betrachtete Problem ist das Einfügen einer zusätzlichen Kante in einen planaren Graphen mit möglichst wenigen Kreuzungen. Dies is der erste Algorithmus, der das Problem löst und er hat lineare Laufzeit. Das zweite Problem ist das Berechnen einer orthogonalen Zeichnung mit der minimalen Anzahl von Knicken. Es ist bekannt, dass dieses Problem NP-schwer ist. Hier benutzen wir den SPQR-Baum, um ein ganzzahliges lineares Programm zu entwickeln, dessen Lösungen den Einbettungen des Graphen entsprechen. Dies ist die Grundlage für unseren Algorithmus für die Berechnung einer knick-minimalen Zeichnung, der sich in unseren Experimenten im Vergleich mit der bisher verwendeten Methode überlegen gezeigt hat.