Abstract. 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.
Merrick and Gudmundsson describe a path simplification method which restricts the number of directions that lines can take REF .
Path Simplification for Metro Map Layout
Graph Drawing
Computer Science