Schnelles Zeichnen von komplexen Beziehungen

KaDraw zeichnet komplexe Graphen effizienter und optimiert deren Darstellung. Grafik: Dr. Christian Schulz, KIT

Die Qualitätskriterien für eine lesbare grafische Darstellung komplexer Beziehungen sind hoch. Beispielsweise müssen die Knotenpunkte weit genug auseinander liegen, um als solche erfasst werden zu können. Gleichzeitig muss das Graphzeichnungstool alle Kanten so anordnen, dass sie für den Betrachter erkennbar bleiben und nicht willkürlich übereinander liegen.

Alle zu beachtenden Kriterien werden deshalb in einer Zielfunktion formuliert. Um diese zu optimieren und gleichzeitig die Effizienz bei der Berechnung zu steigern, hat das Team um Christian Schulz, Henning Meyerhenke und Martin Nöllenburg vom Institut für Theoretische Informatik am KIT das Graphzeichnungstool „KaDraw“ entwickelt.

Bei „KaDraw“ kommen zwei Methoden zum Einsatz. Zum einen bedient man sich der Parallelisierung durch Nutzung von Mehrkernprozessoren. So kann die Rechenleistung gesteigert werden, indem die Rechenlast auf mehrere Prozessorkerne verteilt wird. Zum anderen werden innovative Algorithmen verwendet. Diese Algorithmen erzeugen aus dem komplexen Eingabegraphen zunächst eine Hierarchie von immer kleiner werdenden Graphen.

Um eine gute Darstellung des Eingabegraphen zu erhalten, wird zunächst der kleinste Graph gezeichnet. Die Zeichnung wird danach stückweise auf die größeren Graphen übertragen und auf jedem größeren Level verbessert. „Mit dieser Methode können wir den Zeichenvorgang um ein Vielfaches beschleunigen. KaDraw kann Graphen etwa 30 Mal schneller zeichnen als vorherige Werkzeuge. Dabei bleibt die Qualität des Ergebnisses immer noch vergleichbar“, berichtet Christian Schulz.

Doch nicht nur statische Graphen können durch „KaDraw“ schneller gezeichnet werden. Auch dynamische Graphen, also Graphen, deren Beziehungen sich im Laufe der Zeit verändern, können mit dem Karlsruher System deutlich effizienter bearbeitet werden. Ein Beispiel für dynamische Graphen sind die Freundschaftsbeziehungen in sozialen Netzwerken. Diese unterliegen – etwa durch hinzukommende Freundschaften – einer stetigen Veränderung. „Bei dynamischen Graphen kann man eine bereits vorhandene Zeichnung in unser System eingeben und daraus ein neues Layout mit neuen Beziehungen zeichnen lassen“, erklärt Henning Meyerhenke.

Freie Software

Als Nächstes möchten die Wissenschaftler ein noch effizienteres Verfahren entwickeln. „Durch Verbesserung der algorithmischen Komplexität möchten wir die Effizienz des Verfahrens noch weiter steigern“, sagt Martin Nöllenburg. Doch bevor man sich den neuen Aufgaben widmet, wird „KaDraw“ der Öffentlichkeit zur Verfügung gestellt. Ab sofort steht das Graphenzeichnungstool unter einer General Public License (GPL) zur Verfügung. Zeitgleich präsentieren die Wissenschaftler ihr Tool auf der Fachtagung „Graph Drawing and Network Visualization“.

Link zum Download von KaDraw: http://algo2.iti.kit.edu/kadraw/

Weiterer Kontakt: Nils Ehrenberg, Pressereferent, Tel.: +49 721 608-48122, Fax: +49 721 608-43658, E-Mail: nils.ehrenberg@kit.edu

Das Karlsruher Institut für Technologie (KIT) vereint als selbstständige Körperschaft des öffentlichen Rechts die Aufgaben einer Universität des Landes Baden-Württemberg und eines nationalen Forschungszentrums in der Helmholtz-Gemeinschaft. Seine Kernaufgaben Forschung, Lehre und Innovation verbindet das KIT zu einer Mission. Mit rund 9 400 Mitarbeiterinnen und Mitarbeitern sowie 24 500 Studierenden ist das KIT eine der großen natur- und ingenieurwissenschaftlichen Forschungs- und Lehreinrichtungen Europas.

Das KIT ist seit 2010 als familiengerechte Hochschule zertifiziert.

Diese Presseinformation ist im Internet abrufbar unter: www.kit.edu

Das Foto steht in druckfähiger Qualität auf www.kit.edu zum Download bereit und kann angefordert werden unter: presse@kit.edu oder +49 721 608-47414. Die Verwendung des Bildes ist ausschließlich in dem oben genannten Zusammenhang gestattet.

http://www.kit.edu/kit/pi_2015_109_schnelles-zeichnen-von-komplexen-beziehungen….

Media Contact

Monika Landgraf Karlsruher Institut für Technologie

Alle Nachrichten aus der Kategorie: Informationstechnologie

Neuerungen und Entwicklungen auf den Gebieten der Informations- und Datenverarbeitung sowie der dafür benötigten Hardware finden Sie hier zusammengefasst.

Unter anderem erhalten Sie Informationen aus den Teilbereichen: IT-Dienstleistungen, IT-Architektur, IT-Management und Telekommunikation.

Zurück zur Startseite

Kommentare (0)

Schreiben Sie einen Kommentar

Neueste Beiträge

Neues topologisches Metamaterial

… verstärkt Schallwellen exponentiell. Wissenschaftlerinnen und Wissenschaftler am niederländischen Forschungsinstitut AMOLF haben in einer internationalen Kollaboration ein neuartiges Metamaterial entwickelt, durch das sich Schallwellen auf völlig neue Art und Weise…

Astronomen entdecken starke Magnetfelder

… am Rand des zentralen schwarzen Lochs der Milchstraße. Ein neues Bild des Event Horizon Telescope (EHT) hat starke und geordnete Magnetfelder aufgespürt, die vom Rand des supermassereichen schwarzen Lochs…

Faktor für die Gehirnexpansion beim Menschen

Was unterscheidet uns Menschen von anderen Lebewesen? Der Schlüssel liegt im Neokortex, der äußeren Schicht des Gehirns. Diese Gehirnregion ermöglicht uns abstraktes Denken, Kunst und komplexe Sprache. Ein internationales Forschungsteam…

Partner & Förderer