Rubriken

Veranstaltungen

Advances on 1-planar graphs

Vortrag

Icon Hagener Forschungsdialog
Wann: 03.07.2017 um 14:00 Uhr
Wo: FernUniversität, TGZ-Gebäude, Raum D06 (Erdgeschoss), Universitätsstr. 11, 58097 Hagen
Referent/-in: Dr. Fabrizio Montecchiani, University of Perugia, Italien

Illustration
Dr. Fabrizio Montecchiani, University of Perugia, Italien: PostDoc an der University of Perugia in Italien. Im Jahr 2014 hat Dr. Montecchiani seinen Doktortitel in Computer Engineering an der gleichen Universität erlangt. Er beschäftigt sich hauptsächlich mit Graphenzeichnen, Algorithmischer Geometrie und Algorithm Engineering.
Einführende Worte / Moderation: Dr. Philipp Kindermann (Lehrgebiet Theoretische Informatik)
Veranstalter:Prof. Dr. André Schulz (Lehrgebiet Theoretische Informatik)

Auskunft erteilt: E-Mail an Dr. Philipp Kindermann (Lehrgebiet Theoretische Informatik)

Der Bereich des Graphenzeichnens ist ein recht junges Teilgebiet der theoretischen Informatik und in der Schnittmenge von Graphentheorie und Algorithmischer Geometrie angesiedelt. Es behandelt dabei das Problem, Algorithmen zum automatischen Erzeugen von Graphenvisualisierungen zu finden. Das Ziel ist es, eine “gute” Zeichnung zu finden, was durch unterschiedliche Kriterien gemessen werden kann; zum Beispiel durch die Anzahl der Kreuzungen zwischen Kanten oder durch den Platzverbrauch. Dr. Montecchiani setzt sich hauptsächlich mit dem schweren Problem auseinander, nicht-planare Graphen anschaulich zu zeichnen. Nicht-planare Graphen sind solche, die man nicht kreuzungsfrei zeichnen kann.

Es gibt unterschiedliche Ansätze, dafür zu sorgen, auch für solche Graphen gute Zeichnungen zu kriegen, zum Beispiel indem man Kreuzungen nur mit großen (oder sogar nur rechten) Winkeln erlaubt. Um das Problem etwas einzudämmen, betrachtet man häufig gewissen Graphenklassen, die zwar Kreuzungen haben können, aber nicht zu viele; zum Beispiel Graphen, die man so zeichnen kann, dass jede Kante höchstens einmal gekreuzt wird (1 planare Graphen). In den meisten Fällen ist es schon schwer, für einen gegebenen Graphen zu erkennen, ob er eine solche Zeichnung zulässt. Daher ergeben sich natürliche graphentheoretische Fragestellungen zu Themen wie Charakterisierung, Erkennung, Kantendichte und Färbungszahl der Graphen. Dr. Montecchiani möchte in seinem Vortrag auf diese Eigenschaften eingehen und diverse Visualisierungsmethoden vorstellen.

Beschreibung auf Englisch

The notion of 1-planarity is among the most natural and most studied generalizations of graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at most another edge. The study of 1-planar graphs dates back to more than fifty years ago and, recently, it has driven increasing attention in the areas of graph theory, graph algorithms, graph drawing, and computational geometry.

This talk reviews some of the current literature covering various research streams about 1-planarity, such as characterization and recognition, combinatorial properties, and geometric representations. It also includes relevant open problems.

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