Algorithmen zur kartographischen Schematisierung
Final Report Abstract
Während meines achtmonatigen Forschungsaufenthaltes habe ich an mehreren Themen aus dem Bereich der kartographischen Schematisierung und verwandten Visualisierungsproblemen geforscht. Ein erster Schwerpunkt lag auf der schematischen Visualisierung von Routen in Straßennetzen unter Verwendung einer vorgegebenen Menge C von Kantenrichtungen. Weiterhin sollte die relative räumliche Beziehung der Eingaberoute in Bezug auf die vier Himmelsrichtungen für alle Knotenpaare erhalten bleiben. Im allgemeinen Fall konnten wir das Problem als NP-schwer klassifizieren. Für den auch praktisch interessanten Fall von monotonen Eingabepfaden konnten wir jedoch einen effizienten Algorithmus beschreiben. Um dennoch alle Routen schematisieren zu können, formulierten wir das Problem als gemischt-ganzzahliges Programm, das in ersten experimentellen Untersuchungen schnell gute Ergebnisse liefert. Ein weiteres untersuchtes Schematisierungsproblem ist das Layout hierarchischer räumlicher Treemaps, die geographische Regionen in abstrakter Weise als Rechtecke zeigen. Dabei sollen die Nachbarschaftsbeziehungen der Regionen erhalten bleiben. Definiert man eine Hierarchie durch Gruppieren von Regionen zu einer Metaregion auf einer höheren Ebene, stellt sich das erweiterte Problem, auch diese in der Hierarchie höheren Regionen als Rechtecke darzustellen. Je nachdem, ob das Layout der höheren Ebene vorgegeben ist oder nicht, bzw. ob die Nachbarschaften zwischen den Regionen in orientierter Weise betrachtet werde oder nicht, konnten wir effiziente Algorithmen zur Maximierung der Nachbarschaften angeben oder NP-Schwere des Problems zeigen und Approximationsverfahren angeben. Ebenfalls habe ich mich mit dem Problem beschäftigt, eine Menge von Punkten (z.B. in einer Landkarte) mit internen und externen Beschriftungen (Labels) zu versehen. Dabei grenzen die internen Label mit einer festen Ecke an ihren Punkt an und die externen Label liegen am Rand einer Seite der Zeichenfläche und sind durch einen rektilinearen Pfad mit einem Knick zu ihren Punkten verbunden. Interessant ist bei dieser Kombination, dass das allgemeine Problem möglichst viele Punkte mit rein internen Labeln zu versehen als NP-schwer bekannt ist, während die optimalen Beschriftung mit rein externen Labeln in den meisten Fällen polynomiell lösbar ist. In der Kombination der beiden Varianten konnte hier in einigen Fällen die NP-Schwere gezeigt werden, während andere Fälle durch dynamische Programmierung lösbar sind. Schließlich haben wir noch einen neuen, durch das Werk des Künstlers Mark Lombardi inspirierten, Stil für das Zeichnen von Graphen und insbesondere Bäumen untersucht, sogenannte Lombardi-Zeichnungen. Dabei werden die Knoten zwar wie allgemein üblich als Punkte repräsentiert, aber die Kanten durch Kreisbögen statt durch geradlinige Pfade. Weiterhin müssen die inzidenten Kanten um jeden Knoten gleichmäßig um diesen verteilt sein (perfekte Winkelauflösung). In diesem Modell untersuchten wir das Zeichnen geordneter Bäume sowie bestimmter Klassen von Graphen, z.B. d-reguläre oder 2- und 3-degenerierte Graphen.
Publications
- "Adjacency-preserving spatial treemaps." In F. Dehne, J. Iacono, and J.-R. Sack, editors, Proc. 12th International Symposium on Algorithms and Data Structures (WADS'11) , Lecture Notes Comput. Sci. volume 6844, pages 159-170, Springer-Verlag, 2011
K. Buchin, D. Eppstein, M. Löffler, M. Nöllenburg, and R. I. Silveira
- "Drawing trees with perfect angular resolution and polynomial area." In U. Brandes and S. Cornelsen, editors, Proc. 18th International Symposium on Graph Drawing (GD'IO), Lecture Notes in Comput. Sci., volume 6502, pages 183-194, Springer-Verlag, 2011
C. A. Duncan, D. Eppstein, M. T. Goodrich, S. G. Kobourov, and M. Nöllenburg
