Rechtwinkliges Layout von hierarchisch strukturierten Graphen

Zunächst führt Hickl in alle graphentheoretischen und geometrischen Begriffe ein, die zur Beschreibung des Ansatzes nötig sind. Sodann befaßt er sich mit Graph-Grammatiken, insbesondere mit Ableitungen in Graph-Grammatiken, der Sprache einer Graph-Grammatik und speziellen Eigenschaften von Ableitungen und Graph-Sprachen, die zur Klassifikation der nachfolgenden Layout-Probleme herangezogen werden. Zur Betrachtung der Layout-Graph-Grammatiken werden Restriktions-Ableitungen in Layout-Graph-Grammatiken als dynamische Entscheidungsprozesse formuliert. Dies ermöglicht die Lösung der Layout-Probleme mit Hilfe dynamischer Programmierung. Hickl charakterisiert Kostenfunktionen, für die die Top-Down-Optimierung mittels dynamischer Programmierung lösbar ist, und gibt Lösungsverfahren, zusammen mit der benötigten Zeit-Komplexität, für geeignete Kostenfunktionen an. Die Anwendbarkeit der Charakterisierung für die Kostenfunktionen Knickzahl, Fläche und Kreuzungszahl wird aufgezeigt. Es erweist sich, daß sich viele aus der Literatur bekannte Problemstellungen als Layout-Probleme in Hickls Sinne formulieren lassen. Dies weist auf Einsatzmöglichkeiten von Layout-Graph-Grammatiken und die Allgemeinheit des Ansatzes hin. So werden alternative Möglichkeiten diskutiert, mit Hilfe einer Layout-Graph-Grammatik eine Familie von Graphen und deren Layouts zu definieren. Im Anhang finden sich sämtliche Algorithmen und Implementationsdetails, Beispiele für die einzelnen Schritte in Top-Down-Optimierungen, sowie Laufzeit-Tabellen, Literaturverzeichnis und ein Index.