Crossings in Clustered Level Graphs
Kreuzungen in Cluster-Level-Graphen
- Clustered graphs are an enhanced graph model with a recursive clustering of the vertices according to a given nesting relation. This prime technique for expressing coherence of certain parts of the graph is used in many applications, such as biochemical pathways and UML class diagrams. For directed clustered graphs usually level drawings are used, leading to clustered level graphs. In this thesis we analyze the interrelation of clusters and levels and their influence on edge crossings and cluster/edge crossings.
- Cluster-Graphen sind ein erweitertes Graph-Modell mit einem rekursiven Clustering der Knoten entsprechend einer gegebenen Inklusionsrelation. Diese bedeutende Technik um Zusammengehörigkeit bestimmter Teile des Graphen auszudrücken wird in vielen Anwendungen benutzt, etwa biochemischen Reaktionsnetzen oder UML Klassendiagrammen. Für gerichtete Cluster-Graphen werden üblicherweise Level-Zeichnungen verwendet, was zu Cluster-Level-Graphen führt. Diese Arbeit analysiert den Zusammenhang zwischen Clustern und Level und deren Auswirkungen auf Kantenkreuzungen und Cluster/Kanten-Kreuzungen.
Author: | Michael Forster |
---|---|
URN: | urn:nbn:de:bvb:739-opus-481 |
Advisor: | Franz J. Brandenburg |
Document Type: | Doctoral Thesis |
Language: | English |
Year of Completion: | 2004 |
Date of Publication (online): | 2005/02/14 |
Publishing Institution: | Universität Passau |
Granting Institution: | Universität Passau, Fakultät für Informatik und Mathematik |
Date of final exam: | 2005/02/04 |
Release Date: | 2005/02/14 |
Tag: | cluster; constraint; crossing; crossing number; directed acyclic graph; graph drawing; minimization; planar graph |
GND Keyword: | Graphenzeichnen; Azyklischer gerichteter Graph; Cluster; Kreuzung; Minimierung; Planarer Graph; Constraint-Erfüllung; Kreuzungszahl |
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): | Standardbedingung laut Einverständniserklärung |