Informatik  Abteilung 
Betriebssysteme und Verteilte Systeme
Universitšt Oldenburg   

Research Areas & Projects

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

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].

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:

Last change: Apr 26 2000 stiege