Drawing Families of Cuts in a Graph

Abstract

Ein Graph ist eine abstrakte Repräsentation relationaler Daten aufeiner Menge von Individuen. Ein Schnitt in einem Graphen zerteilt dieMenge der Individuen in zwei nicht-leere Teilmengen. In dieser Arbeitwerden Methoden zur Visualisierung von Schnitten und Mengen vonSchnitten eingeführt. Ein Schnitt enthält zwei wichtige Arten vonInformation: die Partition der Menge der Individuen und die Relationenzwischen Individuen verschiedener Teilmengen. Eine Zeichnung einesSchnittes sollte beides graphisch darstellen. Aus einer Zeichnungeiner 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 angedeutetenAnforderungen erfüllen. In Anlehnung an Zeichenmethoden, dieursprünglich für Bipartitionen, d.h. für Schnitte, für die esjeweils keine Relationen zwischen Individuen der selben Teilmenge derIndividuenmenge gibt, entwickelt wurden, werden zunächst Zeichnungenauf parallelen Linien betrachtet. Der Hauptansatz für die Zeichnungvon Familien von Schnitten beruht auf der Tatsache, daß eine einfachegeschlossene Kurve die Ebene in zwei Zusammenhangskomponentenzerteilt. Ein Schnitt kann also durch eine einfache geschlossene Kurverepräsentiert werden, der die beiden Teilmengen der Individuenmengetrennt. Als Spezialfall werden minimale Schnitte betrachtet, d.h.Schnitte, deren beide Teilmengen so wenig wie möglich miteinanderverbunden sind. Für die Familie aller minimalen Schnitte wird eineZeichnung mit achsenparallelen Rechtecken konstruiert. Schließlichuntersuchen wir das Graphmodell der minimal und minimal+1-tenSchnitte eines Graphen.