Drawing Families of Cuts in a Graph

Cornelsen, Sabine

Drawing Families of Cuts in a Graph

Dateien

final.pdf(1.11 MB)

Datum

2003

Publikationstyp

Dissertation

Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache

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.

Fachgebiet (DDC)

510 Mathematik

Schlagwörter

Graphenzeichnen,Graphenalgorithmen,graph drawing,cuts,minimum cuts,cactus model,graph algorithm

Zitieren

ISO 690

CORNELSEN, Sabine, 2003. Drawing Families of Cuts in a Graph [Dissertation]. Konstanz: University of Konstanz

BibTex

@phdthesis{Cornelsen2003Drawi-591,
  year={2003},
  title={Drawing Families of Cuts in a Graph},
  author={Cornelsen, Sabine},
  address={Konstanz},
  school={Universität Konstanz}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/591">
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/591"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/591/1/final.pdf"/>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/591/1/final.pdf"/>
    <dcterms:abstract xml:lang="deu">Ein Graph ist eine abstrakte Repräsentation relationaler Daten auf&lt;br /&gt;einer Menge von Individuen. Ein Schnitt in einem Graphen zerteilt die&lt;br /&gt;Menge der Individuen in zwei nicht-leere Teilmengen. In dieser Arbeit&lt;br /&gt;werden Methoden zur Visualisierung von Schnitten und Mengen von&lt;br /&gt;Schnitten eingeführt. Ein Schnitt enthält zwei wichtige Arten von&lt;br /&gt;Information: die Partition der Menge der Individuen und die Relationen&lt;br /&gt;zwischen Individuen verschiedener Teilmengen. Eine Zeichnung eines&lt;br /&gt;Schnittes sollte beides graphisch darstellen. Aus einer Zeichnung&lt;br /&gt;einer ganzen Familie von Schnitten sollte außerdem genau hervorgehen,&lt;br /&gt;welche Schnitte tatsächlich gemeint sind und welche nicht. - Es werden verschiedene Ansätze vorgestellt, die die oben angedeuteten&lt;br /&gt;Anforderungen erfüllen. In Anlehnung an Zeichenmethoden, die&lt;br /&gt;ursprünglich für Bipartitionen, d.h. für Schnitte, für die es&lt;br /&gt;jeweils keine Relationen zwischen Individuen der selben Teilmenge der&lt;br /&gt;Individuenmenge gibt, entwickelt wurden, werden zunächst Zeichnungen&lt;br /&gt;auf parallelen Linien betrachtet.  Der Hauptansatz für die Zeichnung&lt;br /&gt;von Familien von Schnitten beruht auf der Tatsache, daß eine einfache&lt;br /&gt;geschlossene Kurve die Ebene in zwei Zusammenhangskomponenten&lt;br /&gt;zerteilt. Ein Schnitt kann also durch eine einfache geschlossene Kurve&lt;br /&gt;repräsentiert werden, der die beiden Teilmengen der Individuenmenge&lt;br /&gt;trennt. Als Spezialfall werden minimale Schnitte betrachtet, d.h.&lt;br /&gt;Schnitte, deren beide Teilmengen so wenig wie möglich miteinander&lt;br /&gt;verbunden sind. Für die Familie aller minimalen Schnitte wird eine&lt;br /&gt;Zeichnung mit achsenparallelen Rechtecken konstruiert. Schließlich&lt;br /&gt;untersuchen wir das Graphmodell der minimal und minimal+1-ten&lt;br /&gt;Schnitte eines Graphen.</dcterms:abstract>
    <dc:language>eng</dc:language>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:rights>terms-of-use</dc:rights>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-22T17:45:09Z</dcterms:available>
    <dcterms:title>Drawing Families of Cuts in a Graph</dcterms:title>
    <dcterms:issued>2003</dcterms:issued>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-22T17:45:09Z</dc:date>
    <dc:format>application/pdf</dc:format>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
  </rdf:Description>
</rdf:RDF>

Prüfungsdatum der Dissertation

February 14, 2003

Universitätsbibliographie

Nein