TU Dortmund
Fakultät Informatik
Lehrstuhl für Algorithm Engineering

Planarisierungsverfahren im Automatischen Zeichnen von Graphen

im Rahmen des DFG-SPP 1307


Start

Beteiligte

Publikationen

Open Graph Drawing Framework OGDF

Simultaneous Graph Drawing Tool SGDT

Links

DFG-SPP 1307

Planarisierungsverfahren im Automatischen Zeichnen von Graphen

Das von der DFG im Rahmen des Schwerpunktprogrammes 1307 "Algorithm Engineering" geförderte Projekt ist dem Gebiet des automatischen Zeichnens von Graphen zuzuordnen und hat sich zum Ziel gesetzt, den Transfer der Planarisierungsverfahren, die bisher oft nur akademisch benutzt werden, in die Praxis zu gewährleisten. Hierzu betrachten wir ausgewählte wichtige Anwendungsfälle und versuchen, die für eine Nutzung in realen Anwendungen bestehenden Hemmnisse aus dem Weg zu räumen. Dies erreichen wir zum einen durch die Einbeziehung verschiedener in den Anwendungen notwendiger Nebenbedingungen in die Planarisierungsmethode, zum anderen durch die Bereitstellung von Open Source Software (s. OGDF) sowie geeigneter Benchmarkinstanzen.

Die Anwendungsbereiche umfassen aus derzeitiger Sicht Visualisierungen im Software-Engineering und schwerpunktmäßig in der Biochemie, wie z.B. Visualisierung metabolischer Netze und Protein-Interaktionsnetzen. Wir werden unsere Ergebnisse einem kontinuierlichen "Algorithm Engineering" unterwerfen, dessen Rückkopplungsschleife wesentlich von unseren Kooperationspartnern aus den betrachteten Anwendungen beeinflusst wird. Dazu haben wir bereits Kontakte aufgenommen und Kooperationszusagen bekommen, welche die Bereitstellung praxisrelevanter Daten, die Unterstützung bei der Erstellung eines Anforderungsprofils und die kritische Begutachtung der von uns zu erstellenden Layouts einschließen.

Die für dieses Projekt relevanten Einbettungsmethoden basieren auf

  1. der Berechnung eines maximal/maximum planaren Subgraphen gefolgt von der kreuzungsvermeidenden Einfügung der entfernten Kanten (planarization),
  2. wie 1. unter Berücksichtigung gewisser Einbettungseinschränkungen (embedding constraints), welche die Reihenfolge und Gruppierung der zu einem Knoten inzidenten Kanten beinhalten (ec-planarization),
  3. wie 1. für azyklische gerichtete Graphen unter Berücksichtigung der induzierten Hierarchie (upward planarization),
  4. der Berechnung eines maximum planaren Subgraphen mittels einer Minimalanzahl von Knotenspaltungen (vertex splitting),
  5. der Berechnung einer gemeinsamen Einbettung zweier oder mehrerer Graphen mit dem Ziel der leichten Erkennbarkeit der Gemeinsamkeiten und Unterschiede (simultaneous embedding).