Geometric Graph Reconstruction

From noisy point samples to road networks and metric graphs.

Filamentary structures—embedded graphs with a metric inherited from the ambient space—show up everywhere in the wild: GPS traces over road networks, earthquake catalogues along plate boundaries, neuronal arbors. This project reconstructs the topology and geometry of such metric graphs from finite, noisy samples around them, both under Gromov–Hausdorff (intrinsic) and Hausdorff (extrinsic, Euclidean) noise models.

Active threads:

• Vietoris–Rips Shadow for Euclidean Graph Reconstruction—with Rafal Komendarczyk and Atish Mitra; reconstruction guarantees under the Hausdorff noise model.
• Reeb-graph reconstruction under relaxed density assumptions—provable schemes when the sample is metrically close only locally.
• Distance measures for geometric graphs—geometric edit distance, graph mover’s distance, and Fréchet-style metrics on the space of embedded graphs.

Collaborators

• Rafal Komendarczyk, Tulane University
• Atish Mitra, Montana Technological University
• Halley Fritze, University of Oregon
• Marissa Masden, University of Puget Sound
• Vitaliy Kurlin, University of Liverpool
• Erin Chambers, St. Louis University (past)
• Carola Wenk, Tulane University (past)

Publications

[1]

H. Fritze, S. Majhi, M. Masden, A. Mitra, and M. Stickney, “Embedded graph reconstruction under Hausdorff noise,” 2024, Available: https://arxiv.org/abs/2410.19410

[2]

S. Majhi, “Graph mover’s distance: An efficiently computable distance measure for geometric graphs,” in Proceedings of the 35th canadian conference on computational geometry, CCCG 2023, Concordia University, Montreal, Quebec, Canada, July 31 - August 4, 2023, D. Pankratov, Ed., 2023, pp. 207–212. Available: https://wadscccg2023.encs.concordia.ca/assets/pdf/CCCG_2023_proc.pdf

[3]

E. Chambers, B. Fasy, B. Holmgren, S. Majhi, and C. Wenk, “Metric and path-connectedness properties of the fréchet distance for paths and graphs,” in Proceedings of the 34th Canadian Conference on Computational Geometry, CCCG 2022, Concordia University, Montreal, QC, Canada, july 31-august 2, 2023, pp. 213–220. Available: https://wadscccg2023.encs.concordia.ca/assets/pdf/CCCG_2023_proc.pdf

[4]

S. Majhi, “Vietoris–Rips complexes of metric spaces near a metric graph,” J. Appl. Comput. Topol., vol. 7, no. 4, pp. 741–770, Dec. 2023.

[5]

S. Majhi and C. Wenk, “Distance measures for geometric graphs,” Computational Geometry, vol. 118, p. 102056, 2024, doi: https://doi.org/10.1016/j.comgeo.2023.102056