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

M. Nöllenburg, A. Wolff

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    29 Citations (Scopus)

    Abstract

    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.
    Original languageEnglish
    Title of host publicationGraph drawing : 13th international symposium, GD 2005, Limerick, Ireland, September 12-14, 2005. : revised papers
    EditorsP. Healy, N.S. Nikolov
    Place of PublicationBerlin
    PublisherSpringer
    Pages321-333
    ISBN (Print)3-540-31425-3
    DOIs
    Publication statusPublished - 2005

    Publication series

    NameLecture Notes in Computer Science
    Volume3843
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'A mixed-integer program for drawing high-quality metro maps'. Together they form a unique fingerprint.

    Cite this