20071201
Linearspace algorithms for distance preserving embedding
Publication
Publication
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2dimensional Euclidean space so that for each edge the distance between their corresponding endpoints is as close to the weight of the edge as possible. If the given graph is complete, that is, if distance constraints are given as a full matrix, then principal coordinate analysis can solve it in polynomial time. A serious disadvantage is its quadratic space requirement. In this paper we develop linearspace algorithms for this problem. A key idea is to partition a set of n objects into disjoint subsets (clusters) of size O(√n) such that the minimum inter cluster distance is maximized among all possible such partitions.
Additional Metadata  

Conference  19th Annual Canadian Conference on Computational Geometry, CCCG 2007 
Citation 
Asano, T. (Tetsuo), Bose, P, Carmi, P. (Paz), Maheshwari, A, Shu, C. (Chang), Smid, M, & Wuhrer, S. (Stefanie). (2007). Linearspace algorithms for distance preserving embedding. Presented at the 19th Annual Canadian Conference on Computational Geometry, CCCG 2007.
