A mixed-integer program for drawing high-quality metro maps

M. Nöllenburg, A. Wolff

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    31 Citaten (Scopus)


    In this paper we investigate 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), draw G and L nicely. We first specify the niceness of a drawing by listing a number of hard and soft constraints. Then we present a mixed-integer 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. We have implemented both the MIP and the heuristics. We compare their output to that of previous algorithms for drawing metro maps and to official metro maps drawn by graphic designers.
    Originele taal-2Engels
    TitelGraph drawing : 13th international symposium, GD 2005, Limerick, Ireland, September 12-14, 2005. : revised papers
    RedacteurenP. Healy, N.S. Nikolov
    Plaats van productieBerlin
    ISBN van geprinte versie3-540-31425-3
    StatusGepubliceerd - 2005

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'A mixed-integer program for drawing high-quality metro maps'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit