Rubriken

Veranstaltungen

„Kanonische Ordnungen und die Mondshein-Sequenz“

Vortrag

Icon Hagener Forschungsdialog
Wann: 11.05.2016 um 14:00 Uhr
Wo: FernUniversität, Informatikzentrum, Universitätsstr. 1, 58097 Hagen, 4. Etage, Raum E08
Referent/-in: Prof Dr. Jens Schmidt (TU Ilmenau)

Illustration

Im Kolloquiumsvortrag werden kanonische Ordnungen von planaren Graphen vorgestellt. Diese Ordnungen haben vielfältige Anwendungen in der Graphtheorie. Insbesondere bilden Sie ein wichtiges Werzeug beim Zeichnen von Graphen. Bei nicht-planaren Graphen gibt es mit der Mondshein Sequenz ein verwandtes Konzept. Im Vortrag werden beide Techniken vorgestellt und Anwendungen aus dem Gebiet des Graphenzeichnens erläutert.

Prof Dr. Jens Schmidt: forscht an der TU Ilmenau zu Themen der Graphentheorie. Sein Spezialgebiet sind Graphen mit starkem Zusammenhang und Zertifikate für Grapheigenschaften.
Veranstalter:Prof. Dr. André Schulz, Lehrgebiet Theoretische Informatik

Auskunft erteilt: Prof. Dr. André Schulz, Lehrgebiet Theoretische Informatik, FernUniversität in Hagen, Universitätsstrasse 1, 58097 Hagen

Kanonische Ordnungen sind heutzutage eine Schlüsselmethode für planare Graphen. Neben den klassischen Anwendungsgebieten wie dem Zeichnen einer gegebenen planaren Einbettung eines Graphens (Chrobak & Payne) zeigt dieser Vortrag, wie kanonische Ordnungen auf nicht-planare Graphen generalisiert werden können.

Diese Generalisierung geht auf eine weitgehend unbekannte Dissertation von Lee Mondshein 1971 am M.I.T. zurück. In dieser zeigt Mondshein die Existenz einer Totalordnung auf den Knoten eines 3-zusammenhängenden Graphens, so dass die Knoten 1,...,i für jedes i einen im Wesentlichen 2-zusammenhängenden Graphen induzieren, während die verbleibenden Knoten i+1,...,n einen zusammenhängenden Graphen induzieren. Mondsheins Sequenz generalisiert kanonische Ordnungen und wurde später und unabhängig von diesen unter dem Namen nicht-separierende Ohrendekomposition bekannt.

Der Vortrag zeigt den bisher unbekannten fundamentalen Bezug zwischen diesen beiden Notationen und erläutert Anwendungen der Mondshein-Sequenz in der Graphentheorie und im Graphenzeichnen.

Gerd Dapprich | 28.04.2016
FernUni-Logo FernUniversität in Hagen, 58084 Hagen, Telefon: +49 2331 987-01, E-Mail: fernuni@fernuni-hagen.de