A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving Distance
<|reference_start|>A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving Distance: Geometric graphs appear in many real-world data sets, such as road networks, sensor networks, and molecules. We investigate the notion of distance between embedded graphs and present a metric to measure the distance between two geometric graphs via merge trees. In order to preserve as much useful information as possible from the original data, we introduce a way of rotating the sublevel set to obtain the merge trees via the idea of the directional transform. We represent the merge trees using a surjective multi-labeling scheme and then compute the distance between two representative matrices. We show some theoretically desirable qualities and present two methods of computation: approximation via sampling and exact distance using a kinetic data structure, both in polynomial time. We illustrate its utility by implementing it on two data sets.<|reference_end|>
@article{chambers2024a,
    title={A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving
  Distance},
    author={Erin Wolf Chambers, Elizabeth Munch, Sarah Percival, Xinyi Wang},
    journal={arXiv preprint arXiv:2407.09442},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.09442},
    primaryClass={cs.DS cs.CG math.GN}
}