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, Karlsruhe, Germany , pp. 258-269 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_26).

Full text not available from this repository.

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.

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
ID Code:781

Repository Staff Only: item control page

References

H. Alt and M. Godau. Measuring the resemblance of polygonal curves. In Proc. 8th Annual Symposium on Computational Geometry, p. 102-109, 1992.

P. K. Agarwal and K. R. Varadarajan. Efficient Algorithms for Approximating Polygonal Chains. Discrete Computational & Geometry, 23(2):273-291, 2000.

J. Bose, O. Cheong, S. Cabello, J. Gudmundsson, M. van Kreveld and B. Speckmann. Area-preserving approximations of polygonal paths. J. Discrete Alg., 2006.

G. Barequet, D. Z. Chen, O. Daescu, M. T. Goodrich and J. Snoeyink. Efficiently approximating polygonal paths in three and higher dimensions. Algorithmica, 33(2):150-167, 2002.

S. Cabello, M. de Berg, and M. van Kreveld. Schematization of networks. Computational Geometry and Applications, 30:223-238, 2005.

W. S. Chan and F. Chin. Approximation of polygonal curves with minimum number of line segments or minimum error. IJCGA, 6:59-77, 1996.

D. Z. Chen and O. Daescu. Space-efficient algorithms for approximating polygonal curves in two-dimensional space. IJCGA, 13:95-111, 2003.

D. Z. Chen, O. Daescu, J. Hershberger, P. M. Kogge, N. Mi and J. Snoeyink. Polygonal path simplification with angle constraints. CGTA, 32(3):173-187, 2005.

CityRail network map. Web page: http://www.cityrail.info/networkmaps/mainmap.jsp (Accessed 6th Sept 2006).

D. Douglas and T. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer 10(2):112-122, 1973.

D. Eu and G. T. Toussaint. On Approximating Polygonal Curves in Two and Three Dimensions. CVGIP: Graphical Model and Image Processing, 56(3):231-246, 1994.

C. Friedrich. jjGraph. Personal communication.

M. T. Goodrich. Efficient piecewise-linear function approximation using the uniform metric. Discrete & Computational Geometry, 14:445-462, 1995.

J. Gudmundsson, M. van Kreveld and D. Merrick. Schematisation of Tree Drawings. Submitted to Graph Drawing, June 2006.

J. Gudmundsson, G. Narasimhan and M. H. M. Smid. Distance-Preserving Approximations of Polygonal Paths. To appear in CGTA, 2006.

L. J. Guibas, J. Hershberger, J. S. B. Mitchell and J. Snoeyink. Approximating Polygons and Subdivisions with Minimum Link Paths. IJCGA, 3(4):383-415, 1993.

J. Hershberger and J. Snoeyink. Cartographic line simplification and polygon CSG formula in O(n log* n) time. Computational Geometry - Theory & Applications, 11(3-4):175-185, 1998.

S.-H. Hong, D. Merrick, and H. A. D. do Nascimento. The metro map layout problem. In Proc. Graph Drawing 2004, p. 482-491, 2005.

H. Imai and M. Iri. Computational-geometric methods for polygonal approximations of a curve. Comp. Vision, Graphics and Image Processing, 36:31-41, 1986.

H. Imai and M. Iri. An optimal algorithm for approximating a piecewise linear function. Journal of Information Processing, 9(3):159-162, 1986.

H. Imai and M. Iri. Polygonal approximations of a curve-formulations and algorithms. In Computational Morphology, G. T. Toussaint (ed.), North-Holland, Amsterdam, 1988.

London Underground network map. Web page: http://www.tfl.gov.uk/tube/maps/ (Accessed 6th Sept 2006).

A. Melkman and J. O'Rourke. On polygonal chain approximation. In Computational Morphology, G. T. Toussaint (ed.), North-Holland, Amsterdam, 1988.

D. Merrick and J. Gudmundsson. Increasing the readability of graph drawings with centrality-based scaling. In Proc. APVIS 2006, p. 67-76, 2006.

D. Merrick and J. Gudmundsson. C-Directed Path Simpli¯cation for Metro Map Layout. http://www.dmist.net/metromap.pdf (Accessed 6th Sept 2006).

G. Neyer. Line simplification with restricted orientations. In Proc. 6th International Workshop on Algorithms and Data Structures, p. 13-24, 1999.

M. Nöllenburg and A. Wolff. A mixed-integer program for drawing high-quality metro maps. In Proc. 13th International Symposium on Graph Drawing, 2005.

J. Stott and P. Rodgers. Metro map layout using multicriteria optimization. In Proc. 8th Interational Conference on Information Visualisation, p. 355-362, 2004.

G. T. Toussaint. On the Complexity of Approximating Polygonal Curves in the Plane. In Proc. of the International Symposium on Robotics and Automation (IASTED), pages 311-318, 1985.