In a road data frame for displaying road maps, each node/link data record describing a link corresponding to a road part includes link identification information identifying an original link, and auxiliary link identification information used for identifying a plurality of alternative links which substitute for any of the original links in the map data. In a route planning data frame for route planning, each connection record describing the interconnection of nodes also includes corresponding link identification information identifying an original link, and corresponding auxiliary link identification information used for identifying a plurality of alternative links which substitute for any of the original links in the map data. By means of identification information of the original link and auxiliary links, it is facilitated to identify the correlation among links in the road data frame and the route planning data frame having different versions.