: Rechtwinkliges Layout von hierarchisch strukturierten Graphen

Rechtwinkliges Layout von hierarchisch strukturierten Graphen

Forschungsergebnisse zur Informatik, Band 23

Hamburg , 312 Seiten

ISBN 978-3-86064-363-1 (Print)

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

Ihr Werk im Verlag Dr. Kovač

Bibliothek, Bücher, Monitore

Möchten Sie Ihre wissenschaftliche Arbeit publizieren? Erfahren Sie mehr über unsere günstigen Konditionen und unseren Service für Autorinnen und Autoren.

Nach oben ▲