Ein kombinatorischer Ansatz für orthogonale Platzierungsprobleme

orthogonalen Platzierungsproblemen aus dem Bereich der
Informationsvisualisierung von einem theoretischen und praktischen
Standpunkt aus. Kernstück ist 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
problemspezifischen 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.