New applications of SPQR-trees in graph drawing

Abstract

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.