Please use this identifier to cite or link to this item:
doi:10.22028/D291-25707
Title: | A combinatorial approach to orthogonal placement problems |
Author(s): | Klau, Gunnar Werner |
Language: | English |
Year of Publication: | 2001 |
SWD key words: | Graph ; Orthogonale Darstellung ; Visualisierung ; NP-hartes Problem ; Kombinatorische Optimierung ; Computerkartographie |
DDC notations: | 004 Computer science, internet |
Publikation type: | Dissertation |
Abstract: | liegt nicht vor! Wir betrachten zwei Familien von NP-schwierigen orthogonalen Platzierungsproblemen aus dem Bereich der Informationsvisualisierung von einem theoretischen und praktischen Standpunkt aus. Diese Arbeit enthält ein gemeinsames kombinatorisches Gerüst für Kompaktierungsprobleme aus dem Bereich des orthogonalen Graphenzeichnens und Beschriftungsprobleme von Punktmengen aus dem Gebiet der Computer-Kartografie. Bei den Kompaktierungsproblemen geht es darum, eine gegebene dimensionslose Beschreibung der orthogonalen Form eines Graphen in eine orthogonale Gitterzeichnung mit kurzen Kanten und geringem Flächenverbrauch zu transformieren. Die Beschriftungsprobleme haben zur Aufgabe, eine gegebene Menge von rechteckigen Labels so zu platzieren, dass eine lesbare Karte entsteht. In einer klassischen Anwendung repräsentieren die Punkte beispielsweise Städte einer Landkarte, und die Labels enthalten die Namen der Städte. Wir präsentieren neue kombinatorische Formulierungen für diese Probleme und verwenden dabei eine pfad- und kreisbasierte graphentheoretische Eigenschaft in einem zugehörigen problemspezifschen Paar von Constraint-Graphen. Die Umformulierung ermöglicht es uns, exakte Algorithmen für die Originalprobleme zu entwickeln. Umfassende experimentelle Studien mit Benchmark-Instanzen aus der Praxis zeigen, dass unsere Algorithmen, die auf linearer Programmierung beruhen, in der Lage sind, große Instanzen der Platzierungsprobleme beweisbar optimal und in kurzer Rechenzeit zu lösen. Ferner kombinieren wir die Formulierungen für Kompaktierungs- und Beschriftungsprobleme und präsentieren einen exakten algorithmischen Ansatz für ein Graphbeschriftungsproblem. Oftmals sind unsere neuen Algorithmen die ersten exakten Algorithmen für die jeweilige Problemvariante. |
Link to this record: | urn:nbn:de:bsz:291-scidok-1968 hdl:20.500.11880/25763 http://dx.doi.org/10.22028/D291-25707 |
Advisor: | Kurt Mehlhorn |
Date of oral examination: | 3-Sep-2001 |
Date of registration: | 22-Apr-2004 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
GunnarWernerKlau_ProfDrKurtMehlhorn.pdf | 1,66 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.