Rechtwinkliges Layout von hierarchisch strukturierten Graphen

Autor*innen

• Timo Hickl

Parameter

• Informatik & Programmierung

Mehr zum Buch

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.

• Sprache: Deutsch
• Erscheinungsdatum: 1996