Map Generalization as a Graph Drawing Problem

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