Die A12 Businessanwendung der Firma mgm technology partners GmbH ist modellgetrieben. Damit die Architektur grafisch dargestellt werden kann, wird ein Layout-System benötigt, an das unterschiedliche Anforderungen gestellt werden. Sie umfassen unter anderem die Minimierungen der Knotenüberschneidungen, der Kantenüberschneidungen und der Biegungen der Kanten.
In der vorliegenden Arbeit werden bereits existierende Layout-Algorithmen betrachtet. Dabei wird besonders darauf geachtet, wie sich diese an die gestellten Anforderungen anpassen lassen. Es stellt sich heraus, dass die Layouts dazu jeweils unterschiedlich gut geeignet sind. Um eine Messbarkeit der Ästhetik zu ermöglichen, werden Metriken definiert.
Es werden zwei Layouts gewählt, welche zur Umsetzung aller Anforderungen besonders geeignet sind. Dabei handelt es sich um das Radial Baum Layout und das kraftgesteuerte Layout, das bereits ein gutes Layout darstellt. Es kann gezeigt werden, dass mithilfe von Anpassungen eine deutliche Verbesserung der Ästhetik von Layouts erreicht wird.
Als Ergebnis der Arbeit entsteht eine Implementierung des kraftgesteuerten Layouts, welche Knotenüberschneidungen fast vollständig eliminiert, ohne dabei andere Aspekte der Graphendarstellung zu stören.
Path decomposition of a graph has received an important amount of interest over the past decades because of its applications in algorithmic graph theory and in real life problems. For the computation of a path decomposition of small width, we use different heuritics approaches. One of the most useful method is by Bodlaender and Kloks. In this thesis, we focus on the computation, applications, transformation and approximation of a path decomposition of small width.
It is easy to convert a path decomposition in to nice path decomposition with same width, which is more convinent to use to find the graph parameters like independent sets, chromatic polynomials etc. Inspired by [28], we find an algorithm to compute the chromatic polynomial of a graph via nice path decomposition with small width.
Diese Arbeit beschäftigt sich mit dem Ising-Polynom, einem Graphenpolynom, das von einem physikalischen Modell abgeleitet ist. Es werden verschiedene Darstellungen des Polynoms, seine Beziehungen zu anderen Graphenpolynomen und in ihm enthaltene Grapheninvarianten vorgestellt. Weiter werden, insbesondere für spezielle Graphenklassen, Berechnungsmöglichkeiten beschrieben und der Rechenaufwand betrachtet.
In dieser Arbeit wird die Klasse der Chordalen Graphen vorgestellt. Dafür werden zunächst einige Grundlagen zu den Chordalen Graphen vorgestellt wie wichtige Definitionen, Eigenschaften, einige Sätze zu dieser Graphenklasse und ein Überblick über wichtige Literatur. Anschließend wird beschrieben, wie man Chordale Graphen erkennen kann und mit welchen anderen Graphenklassen sie im Zusammenhang stehen. Abschließend wird noch auf zwei der bekanntesten Algorithmen für Chordale Graphen eingegangen.