U-Bahn-Linienpläne

Linienpläne sind schematische Karten für Verkehrsnetze wie z.B. U-Bahnen in Großstädten. Der Fokus liegt beim Zeichnen dieser Linienpläne allerdings, im Gegensatz zu herkömmlichen Karten, weniger auf geographischer Genauigkeit als auf einer möglichst übersichtlichen Darstellung der Netztopologie. Wir formulieren ein gemischt ganzzahliges Programm (MIP), das zu einem gegebenen geographischen Liniennetz einen schematischen Linienplan erzeugt, der mehrere Qualitätskriterien optimiert. Außerdem zeigen wir die NP-Schwere des Problems.

Geographische Karte der U-Bahn in Sydney.

Von unserer Methode erzeugter Linienplan.

Das Beispiel des Linienplans von Sydney, Australien zeigt zu welchem Ergebnis unsere Methode ausgehend von einem geographischen Eingabegraphen kommt. Links ist die Eingabezeichnung abgebildet, auf der rechten Seite befindet sich der Linienplan wie er von unserer Methode berechnet wurde. Die Anforderungen an einen Linienplan unterteilen wir dabei in harte und weiche Kriterien. Die harten Kriterien müssen von jeder Zeichnung erfüllt werden. Dazu gehören u.a. (a) die Einhaltung einer Mindestkantenlänge, (b) der Erhalt der Eingabetopologie und (c) die Oktilinearität der Zeichnung, d.h. die Beschränkung aller Kanten auf horizontale, vertikale und 45-Grad diagonale Strecken. Die weichen Anforderungen sollen so gut wie möglich erfüllt werden. Die Ziele sind hier (a) Minimierung der Knicke entlang der einzelnen U-Bahn-Linien, (b) Beibehaltung der relativen Lage benachbarter Stationen und (c) Minimierung der Gesamtkantenlänge. Am gezeigten Beispiel sieht man, wie sich die harten und weichen Qualitätskriterien auf das Ergebnis auswirken.

Am 3. Mai 2006 erhielt Martin Nöllenburg den NRW Undergraduate Science Award 2005 für die Veröffentlichung „A Mixed-Integer Program for Drawing High-Quality Metro Maps“ [3].

Am 21. Juli 2006 erhielt Martin den Absolventenpreis 2005/06 der Fakultät für Informatik für seine Diplomarbeit „Automated Drawing of Metro Maps“ [4].

Am 16. Juli 2006 erschien in der Frankfurter Allgemeinen Sonntagszeitung Nr. 28/06 der zweiseitige Artikel „Die Schönheit des Untergrundes“ von Klemens Polatschek. Erhältlich über das Archiv der FAZ und bei txtr.

1. Alexander Wolff. Drawing subway maps: A survey. Informatik - Forschung & Entwicklung, 22(1):23-44, 2007. [ html | pdf ]
2. Marc Benkert, Martin Nöllenburg, Takeaki Uno, and Alexander Wolff. Minimizing intra-edge crossings in wiring diagrams and public transport maps. In Michael Kaufmann and Dorothea Wagner, editors, Proc. 14th Internat. Sympos. Graph Drawing (GD'06), volume 4372 of Lecture Notes in Computer Science, pages 270-281. Springer-Verlag, 2007. [ bib | pdf ]
3. Martin Nöllenburg and Alexander Wolff. A mixed-integer program for drawing high-quality metro maps. In Patrick Healy and Nikola S. Nikolov, editors, Proc. 13th Internat. Sympos. Graph Drawing (GD'05), volume 3843 of Lecture Notes in Computer Science, pages 321-333. Springer-Verlag, 2006. [ bib | html | pdf ]
4. Martin Nöllenburg. Automated drawing of metro maps. Master's thesis, Fakultät für Informatik, Universität Karlsruhe, August 2005. [ bib | pdf ]
5. Martin Nöllenburg. Automated drawing of metro maps. Technical Report 2005-25, Fakultät für Informatik, Universität Karlsruhe, 2005. [ bib | html | pdf ]