Methods and apparatus to reduce data transmission in a wireless client-server navigation system. A request for data representative of a map-related feature is received at a server from a mobile client. Data describing the feature is obtained in the form of coordinates of line segments. An operation is performed on the data to generate data representative of the feature in a data-reduced format, and the reduced data is forwarded to the client. The operation responsible for producing the data-reduced format includes the steps of: receiving map data; partitioning the map into a plurality of tiles; designating a reference point within each tile; representing the feature in the form of offsets from the reference points; and wherein the data-reduced format is based upon the reference points and offsets. The embodiment may also include sending precalculated turn instruction to the client rather than sending data necessary to generate turn instructions.