Data in the form of one-dimensional structures, embedded or immersed in an ambient space, arise in a variety of applications, including GIS analysis, trajectory clustering, protein alignment, plant morphology, commodity networks such as electrical grids, and geographic networks of roads or rivers. Often one is interested in comparing such structures. But since data collection introduces noise and errors, distance measure need to be robust to different issues in the data.
In this talk we will focus on graphs and provide a survey of distance measures suitable for comparing embedded or immersed graphs. Oftentimes these graphs are not isomorphic, nor is one interested in true subgraph isomorphism. However, it is desirable to have a mapping of one graph to the other, which should fulfill certain properties such as continuity. And the distances should ideally measure differences in geometry and topology. We will examine several distances from mathematical, algorithmic, and applied point of views, and pose open problems for comparing embedded or immersed graphs.