11

„Kanonische Ordnungen und die Mondshein-Sequenz“

11. Mai 2016

Vortrag

Zeitraum
11.05.2016 14:00 Uhr
(bis 15 Uhr)

Ort
FernUniversität, Informatikzentrum, Universitätsstr. 1, 58097 Hagen, 4. Etage, Raum E08

Veranstalter
Prof. Dr. André Schulz, Lehrgebiet Theoretische Informatik

Referent
Prof Dr. Jens Schmidt
TU Ilmenau
forscht an der TU Ilmenau zu Themen der Graphentheorie. Sein Spezialgebiet sind Graphen mit starkem Zusammenhang und Zertifikate für Grapheigenschaften.

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

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.


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 | 06.12.2017