Undirected Graphs

Responsible: Stiege Project Status: active

Als sich der Weg gegabelt,
da ward der Graf gelabelt.
Danach ward er geknebelt
und dann auch noch gelebelt.

Das Wetter war vernebelt.

(chg escalera 1999)

Project description: In undirected graphs, cycles (general closed paths), stopfree cycles, circuits and simple circuits induce equivalence classes of edges which result in a very useful and natural decomposition of undirected graphs into

connected components
stopfree kernels
subcomponents
biblocks (biconnected blocks)

See picture standard decomposition for a schematic representation. The vertices where these components are connected together are border points, check points, and hinge points. The standard decomposition in turn gives rise to a very useful derived graph structure, the biblock graph of an undirected graph. If the original graph is connected, the biblock graph is a tree, the biblock tree. See picture for an example of a biblock tree. Reports [Stie96a], [Stie97], [Stie97a].

In a second step, edge partitions were studied in general. An interesting relationship between sets of vertices and partitions of edges was found, offering a high degree of duality. Partitions which are finest with respect to a given set of attachment vertices W (W-components) are of special interest. As an example, they proved to be very useful in an adaptation of Grünwald's proof of Menger's theorem yielding not only the proof but also an algorithm for finding a maximal set of of vertex-disjoint paths as well as a minimal set of separating vertices. Report [Stie98].

Literature:

[Stie96b]	Günther Stiege Connectivity and Periodicity in Undirected Graphs Institut für Betriebssysteme und Rechnerverbund . November 1996
[Stie97]	Günther Stiege Remarks on Periods and Colorings in Graphs Institut für Betriebssysteme und Rechnerverbund . Februar 1997
[Stie97a]	Günther Stiege An Algorithm for Finding the Connectivity Structure of Undirected Graphs Institut für Betriebssysteme und Rechnerverbund . May 1997
[Stie98]	Günther Stiege Edge Partitions in Undirected Graphs Abteilung Betriebssysteme und Verteilte Systeme . September 1998

Student Theses:

Links:

Last change: Apr 26 2000 stiege