The technique of watermarking has been introduced into 2D vector maps for many potential applications such as protecting the copyright of important GIS (geographical information system) data and tracing the data source of military maps. In most previous works, although the validity of the map data could be preserved during the embedding procedure,the shape-distortions of the map elements are usually neglected which would tend to degrade the invisibility of the watermarking schemes. A shape-preserving algorithm for watermarking 2D vector maps is presented in this paper. A 1D distance sequence extracted from the original map is adopted as the cover data instead of 2D coordinates. A watermark bit is represented by changing the distributions of the cover data. The embedding procedure induces lower shape-distortions than in former works. Experimental results indicate better invisibility of the proposed scheme, as well as its robustness to certain attacks such as map simplification, interpolation, additive noise and most geometric transforms.