Map Generalization as a Graph Drawing Problem

Saalfeld, Alan (1995) Map Generalization as a Graph Drawing Problem. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 444-451 (Official URL:

Full text not available from this repository.


A map may be regarded as a plane graph drawing; and, with the growth of the field of computer cartography, a map is increasingly treated as a straight-line plane graph drawing. Map generalization, the process of redrawing a map at a smaller scale, can, hence, be regarded as a graph drawing problem. The initial version of the map, the input to the process, is a plane graph along with a drawing of that graph. The derived output is also a plane graph that is combinatorially a minor of the input graph. The edges and vertices of the derived graph may be obtained through a sequence of selection and simplification operations. The positioning of those edges and vertices must be obtained through a sequence of placement and displacement operations. Considerable research and development has already been undertaken in the areas of feature selection and simplification. Some generally adequate heuristic solutions to selection and simplification problems are in use today for many types of maps. For other types of maps, such as topographic maps, these solutions are insufficient because they do not simultaneously address the more difficult problems of placement and displacement of features.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_398
Classifications:M Methods > M.999 Others
J Applications > J.999 Others
Z Theory > Z.250 Geometry
ID Code:256

Repository Staff Only: item control page


Kate Beard. How to survive a single detailed database. In AUTOCARTO 8: Proc. of the Eighth International Symposium on Computer-Assisted Cartography, pages 211-220, 1987.

Barbara Buttenfield and David Mark. Expert systems in cartographic design. In Geographic Information Systems: The Computer and Contemporary Cartography, pages 129-150, Pergamon Press, Oxford, 1991.

Barbara Buttenfield and Robert McMaster, editors. Map Generalization: Making Rules for Knowledge Representation. Longman Scientific and Technical, Essex, England, 1991.

Kurt Brassel and Ron Weibel. A review and conceptual framework of automated map generalization. International Journal of Geographical Information Systems, 2(3):229-244, 1988.

D.R. Cardwell, S. Zoratser, and M. Hugus. Automating generalization and M. Hugus. Automating generalization and displacement lessons from manual methods. In Technical Papers: 44th Annual American Congress on Surveying and Mapping (ACSM) Meeting, pages 254-263, 1984.

David Douglas and Tom Peicker. Algorithms for the reduction of the number of points required to represent an line or its caricature. The Canadian Cartographer, 10(2): 112-123, 1973.

Robin Feagas et al. Implementing the spatial data transfer standart. In Joel MOrrison and Kathryn Wortman, editors, Cartography and Geographic Information Systems Special Issue on SDTS, ACSM. December 1992.

D. Lee. Cartographic generalization. Technical Report, Intergraph Corporation, April 1992.

Joel Morrison. A theoretical framework for cartographic generalization with emphasis on the process of symbolization. International Yearbook of Cartography, 14:115-127, 1974.

Brad Nickerson. Automated cartographic generalization for linear features. Cartographica, 25(3):15-66, 1988.

R. Ramirez. Cartographic generalization of topographic maps: the heuristic approach. Technical Report, Ohio State University, 1992.

L. Ratajski. Phénomènes des points de généralization, International Yearbook of Cartography, 7:143-151, 1967.

S. Zoraster, D. Davis, and M. Hugus. Manual and automated line generalization and feature displacement. Technical Report ETL-0359, Engineer Topographic Laboratories, June 1984.