M. Aanjaneya, F. Chazal, D. Chen, M.Glisse, L. Guibas, and D. Morozov, Metric Graph Reconstruction from Noisy Data, 27th Annual ACM Sympoium on Computational Geometry, 2011.

Abstract:

Many real-world data sets can be viewed of as noisy samples of special types of metric spaces called metric graphs [16]. Building on the notions of correspondence and Gromov- Hausdorff distance in metric geometry, we describe a model for such data sets as an approximation of an underlying met- ric graph. We present a novel algorithm that takes as an input such a data set, and outputs the underlying metric graph with guarantees. We also implement the algorithm, and evaluate its performance on a variety of real world data sets.

Bibtex: 

@inproceedings{accggm-mgrnd-11,
 author = {Mridul Aanjaneya and Frederic Chazal and Daniel Chen and Marc Glisse and Leonidas Guibas and Dmitriy Morozov},
 title = {Metric Graph Reconstruction from Noisy Data},
 booktitle="Proc. of the 27th ACM Symposium on Computational Geometry (SoCG'11)", 
 year = {2011}
 }