In the generalization of a concept, we seek to preserve the essential characteristics and behavior of objects. In map generalization, the appropriate selection and application of procedures (such as merging, exaggeration, and selection) require information at the geometric, attribute, and topological levels. This article highlights the potential of graph theoretic representations in providing the topological information necessary for the efficient and effective application of specific generalization procedures. Besides ease of algebraic manipulation, the principal benefit of a graph theoretic approach is the ability to detect and thus preserve topological characteristics of map objects such as isolation, adjacency, and connectivity. While it is true that topologically based systems have been developed for consistency checking and error detection during editing, this article emphasizes the benefits from a map-generalization perspective. Examples are given with respect to specific generalization procedures and are summarized as a partial set of rules for potential inclusion in a cartographic knowledge-based system.