KIT | KIT-Bibliothek | Impressum
Open Access Logo
URN: urn:nbn:de:swb:90-41237

Automated drawing of metro maps

Nöllenburg, Martin

This work investigates the problem of drawing metro maps which is defined as follows. Given a planar graph G of maximum degree 8 with its embedding and vertex locations (e.g. the physical location of the tracks and stations of a metro system) and a set L of paths or cycles in G (e.g. metro lines) such that each edge of G belongs to at least one element of L, draw G and L nicely. We first specify the niceness of a drawing by listing a number of hard and soft constraints. Then we show that it is NP-complete to decide whether a drawing of G satisfying all hard constraints exists. In spite of the hardness of the problem we present a mixed-integer linear program (MIP) which always finds a drawing that fulfills all hard constraints (if such a drawing exists) and optimizes a weighted sum of costs corresponding to the soft constraints. We also describe some heuristics that speed up the MIP and we show how to include vertex labels in the drawing. We have implemented the MIP, the heuristics and the vertex labeling. For six real-world examples we compare our results to official metro maps drawn by graphic designers and to the results of previo ... mehr

Zugehörige Institution(en) am KIT Fakultät für Informatik (INFORMATIK)
Publikationstyp Forschungsbericht
Jahr 2005
Sprache Englisch
Identifikator ISSN: 1432-7864
URN: urn:nbn:de:swb:90-41237
KITopen ID: 1000004123
Verlag Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2005,25
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page