16.05.2013

Informatik-Kolloquium

Im Sommersemester 2013 findet im Rahmen des Informatik-Kolloquiums der folgende Vortrag statt:

Donnerstag, 16. Mai 2013, 16:15 Uhr, Übungsraum II

Dr. Torsten Ueckerdt (Arbeitsgruppe Diskrete Mathematik, Karlsruher Institut für Technologie)

Geometrische Schnittgraphen - von sich schneidenden Boxen und sich küssenden Kreisen

Wir betrachten sogenannte geometrische Überschneidungsgraphen, also Graphen, deren Knoten durch geometrische Objekte und deren Kanten durch sich schneidende Objekte gegeben sind. Durch das Einschränken auf bestimmte geometrische Objekte (zum Beispiel betrachten wir ausschließlich Kreisscheiben in der Ebene) und/oder auf bestimmte Überschneidungsarten (zum Beispiel dürfen sich Objekte nur berühren und nicht überlappen) erhalten wir viele interessante Klassen von Graphen. Solche Graphen sind nicht nur von besonderem ästhetischen Interesse; sie tauchen auch immer wieder in Anwendungen auf.

Wir präsentieren einen Überblick sowohl der wichtigsten klassischen Ergebnisse zu geometrischen Überschneidungsgraphen, als auch neue Entwicklungen und interessante Fragen auf diesem Gebiet.