A map data delivering device for delivering map data to a communication terminal, comprising: a map data storage unit which is configured to store, for each of links that are map components constituting roads on a map, link data composed of point sequence data indicating coordinate values which define position and shape of the corresponding link, attribute data (1022, 1024) indicating at least one type of attribute of the corresponding link, and date and time information indicating a most recent update date and time of the point sequence data; map delivery request receiving means which is configured to receive from the communication terminal a map delivery request containing at least area information indicating a requested area, a map of which is requested to be delivered; map component retrieving means which is configured to search the map data storage unit according to the map delivery request received in the map delivery request receiving means; and map component delivering means (104, 101) which is configured to send the link data searched for by the map component retrieving means to the communication terminal, wherein the map delivery request further contains date and time information indicating a previous map delivery request date and time for the requested area, a map of which is requested to be delivered; the link data stored in the map data storage unit further contains, for each of the links, update propagation range data composed of point sequence data of other links that are other than the corresponding link and whose connected relation is affected by a change in the corresponding link; the map component retrieving means is further configured to extract, from the map data storage unit, every piece of link data associated with update propagation range data covering a link that belongs, at least partly, to the requested area indicated by the area information contained in the map delivery request, and to search the extracted pieces of link data for limited pieces of link data associated with the date and time information indicating the most recent update date and time of the point sequence data that is newer than the previous map delivery request date and time indicated in the map delivery request, wherein the link that belongs, at least partly, to the requested area is a link whose point sequence data has a coordinate value that is within the requested area, or has two adjacent coordinate values that form a line intersecting the requested area. a map data storage unit which is configured to store, for each of links that are map components constituting roads on a map, link data composed of point sequence data indicating coordinate values which define position and shape of the corresponding link, attribute data (1022, 1024) indicating at least one type of attribute of the corresponding link, and date and time information indicating a most recent update date and time of the point sequence data; map delivery request receiving means which is configured to receive from the communication terminal a map delivery request containing at least area information indicating a requested area, a map of which is requested to be delivered; map component retrieving means which is configured to search the map data storage unit according to the map delivery request received in the map delivery request receiving means; and map component delivering means (104, 101) which is configured to send the link data searched for by the map component retrieving means to the communication terminal, wherein the map delivery request further contains date and time information indicating a previous map delivery request date and time for the requested area, a map of which is requested to be delivered; the link data stored in the map data storage unit further contains, for each of the links, update propagation range data composed of point sequence data of other links that are other than the corresponding link and whose connected relation is affected by a change in the corresponding link; the map component retrieving means is further configured to extract, from the map data storage unit, every piece of link data associated with update propagation range data covering a link that belongs, at least partly, to the requested area indicated by the area information contained in the map delivery request, and to search the extracted pieces of link data for limited pieces of link data associated with the date and time information indicating the most recent update date and time of the point sequence data that is newer than the previous map delivery request date and time indicated in the map delivery request, wherein the link that belongs, at least partly, to the requested area is a link whose point sequence data has a coordinate value that is within the requested area, or has two adjacent coordinate values that form a line intersecting the requested area.