Graphenvisualisierung
Graphen sind nicht nur ein häufiges Hilfsmittel beim Modellieren und Lösen von Problemen in der Informatik, sondern werden auch oft zur Visualisierung von Daten genutzt. Auch für Laien sind konkrete Zeichnungen von Graphen oft gut verständlich, da die Darstellung einer Verbindung oder eines Zusammenhangs durch Kanten intuitiv ist. Darüber hinaus lassen sich Methoden zum Zeichnen von Graphen auch oft für das Zeichnen realer Netzwerke, wie z.B. (U-)Bahnnetze, verwenden. Wir entwickeln und untersuchen Algorithmen für das übersichtliche Zeichnen von Graphen.
Es gibt auf dem Gebiet des Graphenzeichnens zwar schon viele beweisbar gute Algorithmen, die aber dennoch keine wirklich übersichtlichen Zeichnungen produzieren. Dies liegt daran, dass es meist schon schwer ist, nur ein gewünschtes Zielkriterium zu optimieren, wie z.B. die Anzahl der Knicke oder der Kreuzungen von Kanten. Dies führt dazu, dass andere Anforderungen an die Übersichtlichkeit einer Zeichnung nicht erfüllt werden, etwa weil die Kanten sehr lang sind oder einzelne Kanten sehr viele Knicke aufweisen. Es kann daher auch sinnvoll sein, Teilprobleme nicht optimal zu lösen, sondern gegeneinander abzuwägen. So kann eine Zeichnung besser lesbar werden, wenn es ein paar Kantenkreuzungen mehr gibt, dafür aber die Kreuzungswinkel sehr groß sind, wodurch die einzelne Kreuzung sehr viel übersichtlicher wird.
Die meisten existierenden Zeichenalgorithmen funktionieren außerdem nur auf planaren Graphen, d.h. Graphen, die sich ohne Überschneidungen zeichnen lassen. Gerade auf realen Daten basierende Graphen sind allerdings oft nicht planar. Haben solche Graphen eine gewisse Größe, was nicht ungewöhnlich ist, so sind in einer Zeichnung die einzelnen Knoten und Kanten ohnehin kaum unterscheidbar. Um die Graphen dennoch vernünftig darstellen zu können, existieren verschiedene Ansätze: man bündelt Gruppen von Kanten oder bildet Knotencluster. Es existiert jedoch noch kein Verfahren, das stets übersichtliche Zeichnungen liefert.
Algorithmische Geometrie
Wie bestimmt man in einer Menge von Punkten am schnellsten zu jedem Punkt seinen nächsten Nachbarn? Wie lässt sich der Durchschnitt von zwei Polygonen effizient berechnen? Wie findet man ein Ziel in unbekannter Umgebung?
Mit diesen und vielen anderen Fragen befasst sich die Algorithmische Geometrie, ein Teilgebiet der Informatik, dessen Entwicklung in den 70er Jahren begann und seitdem einen stürmischen Verlauf genommen hat. Aus gutem Grund: Zum einen ist die Beschäftigung mit geometrischen Problemen selbst sehr reizvoll. Oft gilt es, verborgene strukturelle Eigenschaften aufzudecken, bevor ein effizienter Algorithmus entwickelt werden kann. Zum anderen haben die untersuchten Fragen einen direkten Bezug zu realen Problemen in Anwendungsgebieten wie Computergraphik, Computervision, Geographische Informationssysteme oder Robotik.
Rolf Klein, Vorwort zu Algorithmische Geometrie: Grundlagen, Methoden Anwendungen, 2. Auflage, Springer.
Algorithmische Graphentheorie
Die algorithmische Graphentheorie befasst sich mit der Untersuchung von Graphen und der Entwicklung effizienter Algorithmen zur Lösung von graphentheoretischen Problemen. Ein Graph besteht aus Knoten und Kanten, die miteinander verbunden sind, und kann zur Modellierung von Beziehungen und Netzwerken in vielen Anwendungsgebieten wie Verkehr, Sozialwissenschaften, Biologie oder Computernetzwerken verwendet werden.
In der algorithmischen Graphentheorie werden Algorithmen entwickelt, die zur Lösung von Problemstellungen wie z.B. dem Finden des kürzesten Weges zwischen zwei Knoten, der Bestimmung von Zusammenhangskomponenten oder der Zuordnung von Knoten zu Clustern eingesetzt werden können. Ziel ist es, effiziente Algorithmen zu entwickeln, die diese Probleme schnell und zuverlässig lösen können und somit zur Optimierung von Prozessen und zur Verbesserung von Anwendungen beitragen.