Type of Publication: | Dissertation |
URI (citable link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-9756 |
Author: | Cornelsen, Sabine |
Year of publication: | 2003 |
Summary: |
Ein Graph ist eine abstrakte Repräsentation relationaler Daten auf
einer Menge von Individuen. Ein Schnitt in einem Graphen zerteilt die Menge der Individuen in zwei nicht-leere Teilmengen. In dieser Arbeit werden Methoden zur Visualisierung von Schnitten und Mengen von Schnitten eingeführt. Ein Schnitt enthält zwei wichtige Arten von Information: die Partition der Menge der Individuen und die Relationen zwischen Individuen verschiedener Teilmengen. Eine Zeichnung eines Schnittes sollte beides graphisch darstellen. Aus einer Zeichnung einer ganzen Familie von Schnitten sollte außerdem genau hervorgehen, welche Schnitte tatsächlich gemeint sind und welche nicht. - Es werden verschiedene Ansätze vorgestellt, die die oben angedeuteten Anforderungen erfüllen. In Anlehnung an Zeichenmethoden, die ursprünglich für Bipartitionen, d.h. für Schnitte, für die es jeweils keine Relationen zwischen Individuen der selben Teilmenge der Individuenmenge gibt, entwickelt wurden, werden zunächst Zeichnungen auf parallelen Linien betrachtet. Der Hauptansatz für die Zeichnung von Familien von Schnitten beruht auf der Tatsache, daß eine einfache geschlossene Kurve die Ebene in zwei Zusammenhangskomponenten zerteilt. Ein Schnitt kann also durch eine einfache geschlossene Kurve repräsentiert werden, der die beiden Teilmengen der Individuenmenge trennt. Als Spezialfall werden minimale Schnitte betrachtet, d.h. Schnitte, deren beide Teilmengen so wenig wie möglich miteinander verbunden sind. Für die Familie aller minimalen Schnitte wird eine Zeichnung mit achsenparallelen Rechtecken konstruiert. Schließlich untersuchen wir das Graphmodell der minimal und minimal+1-ten Schnitte eines Graphen. |
Summary in another language: |
A graph is an abstract representation of relational data on a set of
individuals. A cut in a graph divides the set of individuals into two non-empty parts. In this thesis, we introduce methods for visualizing cuts and sets of cuts in a graph. A cut contains two important kinds of information: the partition of the set of individuals and the relations of individuals between different parts. A drawing of a cut should represent both. Besides, a drawing of a set of cuts should exactly indicate which cuts are in the set and which cuts are not. We introduce different approaches that pursue the above mentioned goals. First, we consider drawings on parallel lines -- a method that originally was developed for bipartitions, i.e. for cuts for which there are no relations between individuals of the same part. The main result for drawing families of cuts is based on the fact that every simple closed curve separates the plane into two connected regions. Hence, we can represent a cut by a simple closed curve that separates the two parts of the set of individuals. We consider especially minimum cuts, i.e. cuts for which there are as few relations as possible between the two parts. We show how to construct a drawing with axis-parallel rectangles for the set of all minimum cuts. Finally, we examine the graph model for the set of all minimum and minimum+1 cuts of a graph. |
Examination date (for dissertations): | Feb 14, 2003 |
Dissertation note: | Doctoral dissertation, University of Konstanz |
Subject (DDC): | 510 Mathematics |
Controlled Keywords (GND): | Visualisierung, Graph, Schnitt, Netzwerk, Algorithmus |
Keywords: | Graphenzeichnen, Graphenalgorithmen, graph drawing, cuts, minimum cuts, cactus model, graph algorithm |
Link to License: | In Copyright |
CORNELSEN, Sabine, 2003. Drawing Families of Cuts in a Graph [Dissertation]. Konstanz: University of Konstanz
@phdthesis{Cornelsen2003Drawi-591, title={Drawing Families of Cuts in a Graph}, year={2003}, author={Cornelsen, Sabine}, address={Konstanz}, school={Universität Konstanz} }
final.pdf | 323 |