Rechtwinkliges Layout von hierarchisch strukturierten Graphen

Más información sobre el libro

Hickl führt zunächst in die grundlegenden graphentheoretischen und geometrischen Begriffe ein, die für seinen Ansatz erforderlich sind. Er behandelt Graph-Grammatiken, insbesondere Ableitungen, die Sprache und spezielle Eigenschaften von Ableitungen sowie Graph-Sprachen, die zur Klassifikation von Layout-Problemen dienen. Die Restriktions-Ableitungen in Layout-Graph-Grammatiken werden als dynamische Entscheidungsprozesse formuliert, was die Lösung der Layout-Probleme durch dynamische Programmierung ermöglicht. Hickl beschreibt Kostenfunktionen, für die eine Top-Down-Optimierung mittels dynamischer Programmierung möglich ist, und präsentiert Lösungsverfahren sowie die dazugehörige Zeit-Komplexität für geeignete Kostenfunktionen. Die Anwendbarkeit dieser Charakterisierung wird für die Kostenfunktionen Knickzahl, Fläche und Kreuzungszahl demonstriert. Viele bekannte Problemstellungen aus der Literatur lassen sich als Layout-Probleme im Sinne Hickls formulieren, was auf die Einsatzmöglichkeiten von Layout-Graph-Grammatiken hinweist. Zudem werden alternative Ansätze zur Definition einer Familie von Graphen und deren Layouts mittels Layout-Graph-Grammatiken erörtert. Im Anhang sind Algorithmen, Implementationsdetails, Beispiele für Top-Down-Optimierungen sowie Laufzeit-Tabellen, ein Literaturverzeichnis und ein Index enthalten.