Orthogonal Graph Drawing with Constraints: Algorithms and Applications

Abstract

Die Visualisierung ist ein bewährtes und probates Mittel für die Repräsentation von Daten. Aufgrund der kognitiven Fähigkeiten von Menschen erleichtert eine Visualisierung (graphische Darstellung) das Aufnehmen und Verstehen der in den Daten enthaltenen Informationen. Die vorliegende Arbeit beschäftigt sich mit der Graph-basierten Visualisierung, d. h. der Visualisierung von Daten, die durch Graphen beschrieben werden können.

Ein Graph ist ein Konstrukt der Mathematik (Graphentheorie) und wird zur Modellierung von binären Relationen zwischen Objekten verwendet. Die Objekte werden dabei häufig als Knoten und die Relationen als Kanten bezeichnet. Das Forschungsgebiet, welches sich mit der Visualisierung von Graphen, im Speziellen mit dem automatischen Anordnen (Layout) von Knoten und Kanten beschäftigt, heißt Graphenzeichnen. Beim Zeichnen von Graphen werden Knoten üblicherweise als Punkte/Rechtecke und Kanten als Kurven repräsentiert. Außerdem werden verschiedene ästhetische Anforderungen berücksichtigt, z. B. soll die Anzahl der Kantenkreuzungen in der resultierenden Zeichnung möglichst gering sein.

In orthogonalen Zeichnungen von Graphen werden die Kanten durch Polygonzüge dargestellt, die aus abwechselnd horizontalen und vertikalen Liniensegmenten bestehen. Das bekannteste Verfahren zur Erzeugung von orthogonalen Zeichnungen ist der Topology-Shape-Metrics Ansatz (TSM-Ansatz), der aus den Phasen Planarisierung, Orthogonalisierung und Kompaktierung besteht. Im Gegensatz zu den sogenannten kräftebasierten und hierarchischen Zeichenverfahren, wird der TSM-Ansatz in der Praxis nur selten eingesetzt. Das liegt zum einen an dessen höherem Implementierungsaufwand, zum anderen daran, dass im Vergleich zu den beiden anderen Verfahren nur wenige Erweiterungen zur Einbeziehung von Nebenbedingungen bezüglich der Anordnung der Graphelemente bekannt sind.

Die Formulierung solcher Nebenbedingungen ist notwendig, um geeignete Visualisierungen für Anwendungen aus Bereichen wie Software-Technik, Bioinformatik und Netzwerkanalyse zu erzeugen. In der vorliegenden Arbeit wird ein neues Zeichenverfahren präsentiert, welches auf dem TSM-Ansatz basiert und die folgenden Nebenbedingungen unterstützt:

- Eine Teilmenge der Kanten wird durch monoton steigende Kurven repräsentiert. Diese Kanten besitzen also eine einheitliche Flussrichtung.

- Eine Teilmenge der Knoten wird bimodal gezeichnet, d. h. so, dass die eingehenden und ausgehenden Kanten eines Knotens, bezüglich ihrer Reihenfolge um den Knoten, getrennt voneinander erscheinen.

- Zusammengehörige Knoten werden zu Clustern gruppiert. Jeder Cluster wird durch eine rechteckige Region repräsentiert, welche genau die zum Cluster gehörenden Knoten beinhaltet. Die Position eines Clusters wird dabei nicht vorgegeben.

- Die Zeichenfläche wird in Rechtecke zerlegt. Jeder Knoten wird innerhalb eines vorgegebenen Rechtecks platziert.

- Die möglichen Anschlusspunkte einer Kante an einem dazugehörigen Knoten werden durch die Vorgabe einer Seite oder einer genauen Position am Knotenrand eingeschränkt.

Bislang ist kein TSM-basiertes Verfahren bekannt, dass eine solch komplexe Kombination von Nebenbedingungen zulässt. Für die Entwicklung der entsprechenden Algorithmen wird auf bewährte Methoden und Konzepte aus dem Bereich des Graphenzeichnens zurückgegriffen. Wie der Titel der Arbeit bereits verrät, werden nicht nur neue Algorithmen präsentiert, sondern diese auch im praktischen Einsatz getestet. Die erzielten Ergebnisse bestätigen, dass das Verfahren gut für die Visualisierung praktischer Anwendungen geeignet ist.

In the last two decades, with the emergence of computer graphics, the research field of information visualization has become increasingly important. Information visualization utilizes graphical techniques to support people in understanding and analyzing the information content of data. Due to the capabilities of the human visual system, data represented in (two-dimensional) visual form can be better recognized and understood than data represented in textual or mathematical (one-dimensional) form. In this work we consider graph-based visualizations, i.e., the visualization of data which can be described by graphs.

A graph is a mathematical construct that consists of a set of objects (called vertices) and a set of binary relations between these objects (called edges). Graph drawing, as a branch of graph theory, deals with the design and implementation of automatic layout algorithms for generating readable drawings (diagrams) of graphs. Graphs are usually drawn on a plane using points or rectangles to represent vertices and lines to represent edges. A central problem in graph drawing is how to produce readable drawings, i.e., diagrams that best reveal the information contained in the underlying data. In order to produce such drawings, we have to identify criteria that determine if a drawing is "good" or "bad". Besides general aesthetic criteria like the number of bends or crossings of edges, there are also criteria depending on the semantics and structure of the data.

The most established drawing approaches for general graphs which have received a lot of attention in the graph drawing community are the force-directed approach, the layered approach (also known as the hierarchical approach) as well as the topology-shape-metrics approach (TSM approach) which is based on the orthogonal drawing paradigm (all edges are represented by an alternating sequence of horizontal and vertical line segments). While the first two approaches are very popular in practice and there exist various graph drawing tools supporting them, the TSM approach has never gained this attention there. While all three approaches produce fairly good layout results, the force-directed and layered approaches additionally support several drawing constraints and are easier to implement.

Drawing constraints specify additional requirements for a drawing and are given as additional input to the layout algorithm. Handling drawing constraints is very important for producing adequate visualizations for applications like software engineering, social network analysis and bioinformatics. In this work, we consider the following five drawing constraints:

- Edges of a given set are represented by monotonically increasing curves.

- Incoming edges (and thus outgoing edges) are consecutive with respect to the circular edge order around vertices.

- Given subsets of vertices are placed inside rectangular cluster regions.

- Each vertex is placed inside a predetermined partition cell of a rectangular partitioned drawing area.

- Port constraints specify the exact location (pin) where an edge should leave/enter its incident vertices, while side constraints specify on which side of its incident vertices an edge should leave/enter.

While for some of the above constraints there are already planarization and orthogonalization approaches, there is still no approach which allows one to combine several of these constraints. In this work, we present for the first time an (automatic) orthogonal drawing approach which is based on the TSM approach and is able to include all of the aforementioned constraints at the same time. Therefore, we adapt several sophisticated graph drawing methods and algorithms. As the title of this work suggests, we do not only present algorithms but also demonstrate their efficiency on real-world applications.