Hier gibt's reichlich Material zum Projekt Graphenzeichnen beim BWInf 2012 Workshop.

• Dr. Carsten Gutwenger
• Dr. Karsten Klein

In diesem Workshop beschäftigen wir uns mit dem Zeichenverfahren von Sugiyama, dem Klassiker zum Zeichnen von hierarchischen Graphen. Eine gute Einführung dazu findet sich in der Vorlesung Automatisches Zeichnen von Graphen von Prof. Mutzel. Insbesondere ist hier folgendes Material dieser Vorlesung interessant:

• Vorlesung Sugiyama
  Eine allgemeine Einführung zum Sugiyama-Verfahren, sowie Methoden zur Schichtung des Graphen.

• Vorlesung Kreuzungsminimierung Teil 1 und Teil 2
  Heuristiken zur 2-Schichten Kreuzungsminimierung.

• Skript zum Sugiyama-Verfahren
  Hier wird das gesamte Verfahren nochmal kurz zusammengefasst.

Wir verwenden in diesem Workshop die OGDF-Bibliothek, also das Open Graph Drawing Framework. Infos zu OGDF findet ihr hier:

• Homepage von OGDF.
• Überblick der wichtigsten Datenstrukturen
• Beispiele zur Anwendung des Sugiyama-Layouts: Beispiel 1, Beispiel 2
• Infos für Entwickler, insbesondere die Referenz-Dokumentation der OGDF-Entwicklerversion.

• C++ / Allgemein / Zusätzliche Includeverzeichnisse: C:\Users\BWInf\Documents\OGDF
• C++ / Präprozessor / Präprozessordefinitionen: OGDF_OWN_LPSOLVER (bei Debug zusätzlich OGDF_DEBUG)
• Linker / Eingabe / Zusätzliche Abhängigkeiten: ogdf.lib; Psapi.lib
• Linker / Allgemein / Zusätzliche Bibliotheksverzeichnis: C:\Users\BWInf\Documents\OGDF\Win32\Debug bzw. C:\Users\BWInf\Documents\OGDF\Win32\Release

Zum Testen eurer Implementierungen könnt ihr die folgende Benchmark-Set benutzen. Sie enthält 1214 Graphen im GML-Format mit 20 bis 100 Knoten.

• BWInf-Bench.zip

• GDE Graph-Editor (erfordert Admin-Rechte zur Installation)