Zeichnen von Bäumen auf Gittern

Drawing Trees on Grids

  • Das Zeichnen von Graphen beschäftigt sich mit der Frage, wie die durch einen Graphen repräsentierten Informationen für einen Betrachter übersichtlich und verständlich dargestellt werden können. Die Graphklasse der Bäume dient insbesondere zur Repräsentation von hierarchischen Strukturen. Neben den hierarchisch und radial darstellenden Verfahren werden Bäume auch auf dem orthogonalen Gitter gezeichnet, in welchem die Knoten auf ganzzahligen Koordinaten liegen und die Kanten entlang der horizontalen und vertikalen Gitterlinien verlaufen. Gewünscht wird eine gute Lesbarkeit der Zeichnungen und deren effiziente Berechnung. Für die formale Bewertung der Lesbarkeit existieren speziell für das Zeichnen von Bäumen definierte Ästhetikkriterien, wie eine ebenenweise Darstellung, die Ordnungserhaltung und Kriterien zur Darstellung von Subgraphisomorphien und Symmetrien. Die vorliegende Arbeit befasst sich mit einer bislang wenig studierten Erweiterung des orthogonalen Gitters auf das hexagonale und oktagonale Gitter durch das Hinzunehmen vonDas Zeichnen von Graphen beschäftigt sich mit der Frage, wie die durch einen Graphen repräsentierten Informationen für einen Betrachter übersichtlich und verständlich dargestellt werden können. Die Graphklasse der Bäume dient insbesondere zur Repräsentation von hierarchischen Strukturen. Neben den hierarchisch und radial darstellenden Verfahren werden Bäume auch auf dem orthogonalen Gitter gezeichnet, in welchem die Knoten auf ganzzahligen Koordinaten liegen und die Kanten entlang der horizontalen und vertikalen Gitterlinien verlaufen. Gewünscht wird eine gute Lesbarkeit der Zeichnungen und deren effiziente Berechnung. Für die formale Bewertung der Lesbarkeit existieren speziell für das Zeichnen von Bäumen definierte Ästhetikkriterien, wie eine ebenenweise Darstellung, die Ordnungserhaltung und Kriterien zur Darstellung von Subgraphisomorphien und Symmetrien. Die vorliegende Arbeit befasst sich mit einer bislang wenig studierten Erweiterung des orthogonalen Gitters auf das hexagonale und oktagonale Gitter durch das Hinzunehmen von einer bzw. beider diagonalen Gitterrichtungen, und der Problemstellung, wie Bäume darauf gezeichnet werden. Dadurch können auch Bäume mit einem höheren Grad gezeichnet werden als auf dem orthogonalen Gitter. Die Einschränkung, dass nur Bäume gezeichnet werden können, deren Grad kleiner ist als die Anzahl der Gitterrichtungen des verwendeten Gitters, besteht jedoch weiterhin. Als Ästhetikkriterien werden die lokale Uniformität, die die Länge der ausgehenden Kanten eines Knotens festlegt, und Pattern, die deren Richtungen festlegen, eingeführt. Gegenüber dem bekannten linearen Flächenverbrauch von geradlinigen Zeichnungen von vollständigen Binärbäumen auf dem orthogonalen Gitter, werden für Zeichnungen von vollständigen d-nären Bäumen mit d > 2 nicht-lineare untere Schranken für die benötigte Fläche auf dem hexagonalen und dem oktagonalen Gitter gezeigt. Insgesamt werden für vollständige und beliebige, geordnete und ungeordnete Bäume obere und untere Flächenschranken für Zeichnungen auf dem hexagonalen und oktagonalen Gitter präsentiert. Dabei zeigt sich, dass bei nicht-ordnungserhaltenden Zeichnungen zwar mehr als lineare, aber deutlich weniger als quadratische Fläche benötigt wird. Im Gegensatz dazu gibt es geordnete Bäume, deren ordnungserhaltende Zeichnungen exponentielle Fläche benötigen. Des Weiteren wird die Ermittlung der minimalen Zeichenfläche für geordnete d-näre Bäume ebenso als NP-vollständig bewiesen, wie das Zeichnen von ungeordneten d-nären Bäumen mit einheitlichen Kantenlängen. Schließlich werden zwei Linearzeitalgorithmen vorgestellt, die geordnete d-näre Bäume unter Einhaltung der genannten Ästhetikkriterien zeichnen.show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Marco Matzeder
URN:urn:nbn:de:bvb:739-opus-26923
Advisor:Franz Josef Brandenburg
Document Type:Doctoral Thesis
Language:German
Year of Completion:2012
Date of Publication (online):2013/01/07
Publishing Institution:Universität Passau
Granting Institution:Universität Passau, Fakultät für Informatik und Mathematik
Date of final exam:2012/06/25
Release Date:2013/01/07
Tag:Baumzeichnung; Hexagonales Gitter; Oktagonales Gitter; Orthogonales Gitter; lokale Uniformität; ordnungserhaltend
Grid; Tree Drawing; ordered; unordered
GND Keyword:Baum <Mathematik>; Wald <Graphentheorie>; Graph; Gittereinbettung; Graphenzeichnen; Gitter; Sweep-Algorithmus; Rekursiver Algorithmus
Institutes:Fakultät für Informatik und Mathematik / Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
open_access (DINI-Set):open_access
Licence (German):License LogoStandardbedingung laut Einverständniserklärung