Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Neue Modelle und Methoden zum effektiven orthogonalen Layout von Graphen

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2014 bis 2023
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 249458560
 
Erstellungsjahr 2023

Zusammenfassung der Projektergebnisse

Graph Drawing ist ein sehr aktives Gebiet, das sich mit der sinnvollen Visualisierung von Graphen in der Ebene beschäftigt. Das interdisziplinäre Gebiet vereint Zweige aus der Graphentheorie, der Kombinatorik, der Algorithmik, den Anwendungen und der Benutzerforschung. Während mehrere grundlegende Modelle und Methoden etabliert wurden, sind die praktischen Anforderungen oft nicht berücksichtigt worden. Daher müssen die Modelle verfeinert, analysiert und erforscht werden. Das bekannteste Modell ist das orthogonale Modell, bei dem die Kanten aus horizontalen oder vertikalen Liniensegmenten bestehen und höchstens ein Kantensegment auf jeder der vier möglichen Seiten eines Knotens endet. Das vorliegende Projekt befasste sich mit möglichen Erweiterungen. Wir starteten mit zwei neuen Ansätzen. Im ersten Modell, dem so genannten Smooth Drawing Model (Smog), werden anstelle von achsenparallelen Liniensegmenten Kreisbögen verwendet, die sich an einer gemeinsamen Tangente nahtlos anschließen. Das zweite Modell wird als Slanted Drawing Modell (Slog) bezeichnet. Hier werden die traditionellen 90°-Knicke durch dazwischenliegende diagonale Segmente ersetzt, so daß nur 135°-Knicke zulässig sind, und Kreuzungen werden sichtbarer gemacht, da sie nur zwischen diagonalen Segmenten zulässig sind. In beiden Modellen befinden sich die Anschlüsse für die Kanten nach wie vor an den vier möglichen Seiten der Knoten. Wir wollten vom traditionellen orthogonalen Modell so viele Ergebnisse wie möglich auf die neuen Modelle übertragen und ihre Vorteile demonstrieren und quantifizieren. In der ersten Projektphase konzentrierten wir uns auf diese beiden Modelle, insbesondere auf die Minimierung der Segmentanzahl pro Kante (Knicken), die verwendete Fläche, die Komplexität der Layout-Algorithmen und darüber hinaus auf die Untersuchung von Erweiterungsvarianten. Beide Modelle haben ihre Nachteile (z.B. großer Flächenverbrauch), aber auch schöne Eigenschaften, die übersichtlichere Layouts ermöglichen. Die von uns untersuchten Varianten weisen ebenfalls deutliche Vorteile auf, wenngleich Fragen zur Realisierbarkeit offen bleiben und die Modelle hinsichtlich ihrer Robustheit und Flexibilität für praktische Anwendungen geprüft werden müssen. In der zweiten Projektphase haben wir unsere Forschung zu Erweiterungen des ursprünglichen orthogonalen Modells ausgedehnt, die mehr praktische Aspekte berücksichtigen: Graphenlayouts mit Knoten hohen Grades erfordern viele verschiedene Steigungen auf den Kantensegmenten, wobei die Minimierung der Anzahl der Steigungen die Einheitlichkeit des Layouts unterstützt. Eine andere Richtung, die wir verfolgt haben, sind die sogenannten RAC-Zeichnungen, bei denen die Kreuzungen rechtwinklig sein müssen, die Steigungen der Kanten aber nicht eingeschränkt sind. Insbesondere haben wir Fortschritte bei der Beziehung zwischen Flächenverbrauch und Knicken sowie bei Layouts für Graphen mit begrenztem Grad gemacht. Hinsichtlich des Smog-Modells waren die Layouts, die wir ursprünglich untersucht haben, nur planar, und der Aspekt von Kantenkreuzungen war ganz offen. Dies war ein wichtiger Punkt in unserer zweiten Projektphase.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2025 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung