Neue Modelle und Methoden zum effektiven orthogonalen Layout von Graphen

• Antragsteller: Professor Michael Kaufmann, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 249458560

Orthogonales Graphenzeichnen ist ein intensiv erforschtes und wohl-etabliertes Modell im Graphenzeichnen, welches auf VLSI-Layout und Floor-planning Anwendungen zurückgeht. Wegen seiner hohen Bedeutung in praktischen Anwendungen wurden über die Jahre mehrere effiziente Algorithmen entwickelt, die gute Ästhetik und Lesbarkeit garantieren. Allerdings gibt es auf Grund der inhärenten Einschränkungen, insbesondere auch wegen der Einfachheit des Modells einige Nachteile, die unvermeidbar erscheinen.Für die erste Phase des Projekts haben wir diese Nachteile identifiert und zwei alternative Modelle vorgeschlagen.Das erste Modell ist das geglättete orthogonale Modell (kurz Smog), welches die Klarheit von orthogonalen Layouts mit dem künstlerischen Stil und ästhetischen Eindruck von sogenannten Lombardi-Zeichungen. verbindet. Das zweite Modell ist das abgeschrägte orthogonale Modell (kurz Slog), welches diagonale Kantensegmente erlaubt unter Beibehaltung von originalen orthogonalen Anschlüssen an den Knoten. Dadurch wird insbesondere die Erkennbarkeit der Kreuzungen sehr vereinfacht.In der ersten Projektphase lag der Fokus hauptsächlich auf den methodischen Grundlagen. Für die zweite Phase planen wir, unsere theoretischen Studien weiterzuführen und die in der ersten Phase erworbenen Einsichten auf verschiedene Anwendungen zu übertragen, indem jeweils die anwendungsspezifischen Anforderungen in die Modelle integriert werden.

• DFG-Verfahren: Sachbeihilfen
• Mitverantwortlich: Professor Dr. Michael Bekos