Radiales und zyklisches Zeichnen von Graphen: Layouts auf dem Zylinder

• Applicant: Professor Dr. Franz Josef Brandenburg
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 148338284

Das Zeichnen von Graphen befasst sich mit der Entwicklung von Algorithmen, die Graphen so zeichnen, dass ihre Eigenschaften von einem Benutzer gut erfasst werden können. Ein wichtiges Merkmal ist die Richtung der Kanten. Diese stellen Abhängigkeiten dar und müssen sich in der Zeichnung widerspiegeln. Im klassischen Fall ist die Richtung von oben nach unten. Man hat hierarchische Zeichnungen, die mit dem Sugiyama Algorithmus konstruiert werden. Unser Paradigma sind Zyklen. Diese sollen als Zyklen gezeichnet werden. Dies ist eine Anforderung z.B. bei der Darstellung von Reaktionsdiagrammen oder bei periodisch sich wiederholenden Prozessen. Gegenstand des Vorhabens ist die Optimierung und Weiterentwicklung der radialen und die Neuentwicklung der zyklischen Variante des Sugiyama Algorithmus. Diese synthetisieren sich zur torischen Variante. Zusammen mit dem Standardverfahren ergibt sich ein Framework für alle Anwendungsfälle. Die Aufgabe umfasst Theorie und Praxis. Auf der theoretischen Seite müssen die algorithmischen Probleme hinter den radialen und zyklischen Versionen des Sugiyama Algorithmus studiert werden. Auf der praktischen Seite sind die Verfahren zu implementieren, in das vorhandene Gravisto System zu integrieren und experimentell zu bewerten. Ein besonderes Interesse gilt der Planarität und dem Feedback Arc Set Problem.

• DFG Programme: Research Grants
• Participating Person: Dr. Christian Bachmaier