Crossings, Curves, and Constraints in Graph Drawing

Kreuzungen, Kurven und Constraints beim Zeichnen von Graphen

Please always quote using this URN: urn:nbn:de:bvb:20-opus-98235
  • In many cases, problems, data, or information can be modeled as graphs. Graphs can be used as a tool for modeling in any case where connections between distinguishable objects occur. Any graph consists of a set of objects, called vertices, and a set of connections, called edges, such that any edge connects a pair of vertices. For example, a social network can be modeled by a graph by transforming the users of the network into vertices and friendship relations between users into edges. Also physical networks like computer networks orIn many cases, problems, data, or information can be modeled as graphs. Graphs can be used as a tool for modeling in any case where connections between distinguishable objects occur. Any graph consists of a set of objects, called vertices, and a set of connections, called edges, such that any edge connects a pair of vertices. For example, a social network can be modeled by a graph by transforming the users of the network into vertices and friendship relations between users into edges. Also physical networks like computer networks or transportation networks, for example, the metro network of a city, can be seen as graphs. For making graphs and, thereby, the data that is modeled, well-understandable for users, we need a visualization. Graph drawing deals with algorithms for visualizing graphs. In this thesis, especially the use of crossings and curves is investigated for graph drawing problems under additional constraints. The constraints that occur in the problems investigated in this thesis especially restrict the positions of (a part of) the vertices; this is done either as a hard constraint or as an optimization criterion.show moreshow less
  • Viele Probleme, Informationen oder Daten lassen sich mit Hilfe von Graphen modellieren. Graphen können überall dort eingesetzt werden, wo Verbindungen zwischen unterscheidbaren Objekten auftreten. Ein Graph besteht aus einer Menge von Objekten, genannt Knoten, und einer Menge von Verbindungen, genannt Kanten, zwischen je einem Paar von Knoten. Ein soziales Netzwerk lässt sich etwa als Graph modellieren, indem die teilnehmenden Personen als Knoten und Freundschaftsbeziehungen als Kanten dargestellt werden. Physikalische Netzwerke wie etwaViele Probleme, Informationen oder Daten lassen sich mit Hilfe von Graphen modellieren. Graphen können überall dort eingesetzt werden, wo Verbindungen zwischen unterscheidbaren Objekten auftreten. Ein Graph besteht aus einer Menge von Objekten, genannt Knoten, und einer Menge von Verbindungen, genannt Kanten, zwischen je einem Paar von Knoten. Ein soziales Netzwerk lässt sich etwa als Graph modellieren, indem die teilnehmenden Personen als Knoten und Freundschaftsbeziehungen als Kanten dargestellt werden. Physikalische Netzwerke wie etwa Computernetze oder Transportnetze - wie beispielsweise das U-Bahnliniennetz einer Stadt - lassen sich ebenfalls als Graph auffassen. Um Graphen und die damit modellierten Daten gut erfassen zu können benötigen wir eine Visualisierung. Das Graphenzeichnen befasst sich mit dem Entwickeln von Algorithmen zur Visualisierung von Graphen. Diese Dissertation beschäftigt sich insbesondere mit dem Einsatz von Kreuzungen und Kurven beim Zeichnen von Graphen unter Nebenbedingungen (Constraints). Die in den untersuchten Problemen auftretenden Nebenbedingungen sorgen unter anderem dafür, dass die Lage eines Teils der Knoten - als feste Anforderung oder als Optimierungskriterium - vorgegeben ist.show moreshow less

Download full text files

Export metadata

Metadaten
Author: Martin Fink
URN:urn:nbn:de:bvb:20-opus-98235
Document Type:Doctoral Thesis
Granting Institution:Universität Würzburg, Fakultät für Mathematik und Informatik
Faculties:Fakultät für Mathematik und Informatik / Institut für Informatik
Referee:Prof. Dr. Alexander Wolff, Prof. Dr. Michael Kaufmann
Date of final exam:2014/04/24
Language:English
Year of Completion:2014
Publisher:Würzburg University Press
ISBN:978-3-95826-002-3 (print)
ISBN:978-3-95826-003-0 (online)
Pagenumber:222
DOI:https://doi.org/10.25972/WUP-978-3-95826-003-0
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
GND Keyword:Graphenzeichnen; Kreuzung; Kurve; Graph
Tag:Kreuzungsminimierung; Landkartenbeschriftung; U-Bahnlinienplan
crossing minimization; curves; graph drawing; labeling; metro map
CCS-Classification:F. Theory of Computation / F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (B.6-7, F.1.3) / F.2.2 Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3) / Computations on discrete structures
G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.2 Graph Theory (F.2.2) / Graph algorithms
Release Date:2014/10/16
Licence (German):License LogoCC BY-SA: Creative-Commons-Lizenz: Namensnennung, Weitergabe unter gleichen Bedingungen