Ein planarer Graph (auch plättbarer
Graph) ist in der Graphentheorie
ein Graph,
der auf einer Ebene mit Punkten für die Knoten
und Linien für die Kanten dargestellt werden kann,
so dass sich die Kanten nur in den Knoten schneiden.
Die Planarität eines Graphen lässt sich mit verschiedenen Algorithmen in linearer
Zeit testen. Planarität ist eine der bekanntesten
Grapheigenschaften, und taucht in Theorie und Praxis häufig auf.
Allerdings weiß man nicht viel über zufällige planare Graphen.
Wenn man nur die Isomorphieklassen von planaren
Graphen betrachten (in diesem Fall spricht man auch von nicht beschrifteten planaren
Graphen) ist noch weniger bekannt.
Mitwirkende am Lehrstuhl
- Professor: Prof. Dr. Hans Jürgen Prömel
- Mitarbeiter: Dr. Manuel Bodirsky, Dr. Mihyun Kang
- Studenten: Daniel Johannsen, Dirk Schlatter, Stefan Vigerske
- Ehemalige: Prof. Dr. Anusch Taraz, Dr. Clemens Gröpl, Dr. Deryk Osthus, Mike Löffler
Themen
- Zufällige Strukturen in der Ebene und deren Eigenschaften
- Zählen von planaren Strukturen
- Generierende Funktionen und asymptotische Analyse
- Sampling: Effiziente Generierung gleichverteilt zufälliger planarer Strukturen
Ergebnisse
- Gelabelte planare Graphen: Zufällige planare Graphen; Exakte Enumeration und zufällige Erzeugung
- Kubische planare Graphen: Zufällige gelabelten kubischen planaren Graphen ; Zufällige Erzeugung ungelabelter kubischer planarer Graphen
- Series-parallel und Outerplanare Graphen: Asymptotische Anzahl von gelabelten Series-parallel und Outerplanare Graphen; Asymptotische Anzahl von ungelabelten Outerplanare Graphen; Exakte Enumeration und Zufällige Erzeugung von gelabelten und ungelabelten outerplanaren Graphen
- Zweizusammenhängende planare Graphen: Zufällige Erzeugung von ungelabelten zweizusammenhängende planaren Graphen
- Dreizusammenhängende planare Graphen: Asymptotische Anzahl und zufällige Erzeugung
- Existenz und Aufbau der planaren Subgraphen
- Planare Graphen Prozess
Implementierungen und Daten
- Gelabelte planare Graphen: Enumerierung
- Gelabelte outerplanare Graphen: Sampling; Enumerierung
- Ungelabelte outerplanare Graphen: Enumerierung
- Gelabelte kubische planare Graphen: Sampling; Enumerierung
Anknüpfpunkte in Berlin
- Forschergruppe Algorithmen, Struktur, Zufall
- Forschungsschwerpunkt Diskrete Strukturen
- Approximationsalgorithmen, randomisierte Algorithmen und probabilistische Analyse
- Graduiertenkolleg Combinatorics, Geometry, and Computation
Nützliche Links
- Die online Enzyklopädie für Folgen ganzer Zahlen von Neil J. A. Sloane: http://www.research.att.com/~njas/sequences/
- Das Buch zu Singularitätenanalyse von P. Flajolet and R. Sedgewick: http://algo.inria.fr/flajolet/Publications/AnaCombi1to9.pdf
- Mathematische Konstanten von Steven R. Finch: http://pauillac.inria.fr/algo/bsolve/
- Eine Sammlung von Algorithmen zur Erstellung von Listen kombinatorischer Strukturen von Gunnar Brinkmann und Brendan McKay: http://cs.anu.edu.au/~bdm/plantri/
English