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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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):License LogoStandardbedingung laut Einverständniserklärung