From noisy point samples to road networks and metric graphs.

Research · Plate II
Geometric Graph Reconstruction
Filamentary structures · metric graphs · noisy samples Seven collaborators Updated MMXXVI
A finite set of sample points in the plane, with edges of an embedded graph reconstructed between them.
A finite, noisy sample of points in the plane and the embedded metric graph reconstructed from it—edges, vertices, branch structure.
“Filamentary structures are the world's most common topology, and the most often misread.”

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

The recurring shape of a result: identify a sampling condition—a density & reach assumption, often—under which the Vietoris–Rips or Reeb-graph reconstruction is quasi-isometric to the embedded graph it was drawn from. The work is in finding conditions weak enough to hold for real GPS data and strong enough to admit a theorem.

Active threads

Filed under Theory · Open Problems Three 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

Filed under Co-authors Seven institutions
  • 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