When searching for optimal paths in a network, algorithms like A*-search need an approximation of the minimal costs between the current node and a target node. A reference node embedding is a universal method for making such an approximation working for any type of positive edge weights. A drawback of the approach is that it is necessary to store the shortest distance to each landmark node for each considered attribute. Thus, the memory consumption of the embedding is linearly increasing with the number of attributes and landmarks. Thus, an embedded graph might not be well-suited for handheld devices and may significantly increase the loading cost. In this paper, we propose methods for significantly decreasing the memory consumption of embedded graphs and examine the impact of the landmark selection. Furthermore, we propose to limit the number of embedded nodes in the network and propose an algorithm for shortest path computation working on networks for which only a portion of nodes store an embedding. Finally, we propose a heuristic algorithm for finding a suitable subset of nodes that should be embedded in order to guarantee reasonable computation times. Our experimental evaluation examines the trade-off between embedding memory and processing times on two real-world data sets.