A Mixed-Integer Program for Drawing High-Quality Metro Maps

Nöllenburg, Martin and Wolff, Alexander (2006) A Mixed-Integer Program for Drawing High-Quality Metro Maps. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 321-333(Official URL: http://dx.doi.org/10.1007/11618058_29).

Full text not available from this repository.

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 mathcal L of paths or cycles in G (e.g. metro lines) such that each edge of G belongs to at least one element of mathcal L, draw G and mathcal L emph{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.

Item Type:	Conference Paper
Additional Information:	10.1007/11618058_29
Classifications:	M Methods > M.999 Others M Methods > M.600 Planar P Styles > P.999 Others P Styles > P.540 Planar
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/701

Actions (login required)

View Item