Über das Buch

Zum Inhalt

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. [...]

Schlagworte

, Informatik