Path Simplification for Metro Map Layout

Merrick, Damian and Gudmundsson, Joachim (2007) Path Simplification for Metro Map Layout. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006 , pp. 258-269(Official URL:

Full text not available from this repository.


We investigate the problem of creating simplified representations of polygonal paths. Specifically, we look at a path simplification problem in which line segments of a simplification are required to conform with a restricted set of directions C. An algorithm is given to compute such simplified paths in O(|C|^3 n^2) time, where n is the number of vertices in the original path. This result is extended to produce an algorithm for graphs induced by multiple intersecting paths. The algorithm is applied to construct schematised representations of real world railway networks, in the style of metro maps.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-70904-6_26
Classifications: M Methods > M.900 Tree
G Algorithms and Complexity > G.350 Clusters
J Applications > J.999 Others

Actions (login required)

View Item View Item