This paper proposes a digital watermarking algorithm for 2D vector digital maps. The watermark is a robust, informed-detection watermark to be used to prevent such abuses as an intellectual property rights violation. The algorithm proposed in this paper embeds watermarks in the frequency-domain representation of a 2D vector digital map. Our method treats vertices in the map as a point set, and imposes connectivity among the points by using Delaunay triangulation. The method then computes the mesh-spectral coefficients [Karni00] from the mesh created. Modifications of the coefficients according to the message bits, and inverse transforming the coefficients back into the coordinate domain produces the watermarked map. Our evaluation experiments showed that the watermark produced by the method is resistant against additive random noise, similarity transformation, vertex insertion and removal. It is also resistant, to some extent, against cropping. Compared to our previous algorithm [Ohbuchi02], the algorithm described in this paper showed significantly improved attack resiliency.