03

Advances on 1-planar graphs

03. Juli 2017

Vortrag

Zeitraum
03.07.2017 14:00 Uhr


Ort
FernUniversität, TGZ-Gebäude, Raum D06 (Erdgeschoss), Universitätsstr. 11, 58097 Hagen

Veranstalter
Prof. Dr. André Schulz (Lehrgebiet Theoretische Informatik)

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

Moderation
Dr. Philipp Kindermann (Lehrgebiet Theoretische Informatik)

Auskunft erteilt
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

[mehr erfahren]

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