Distance Measures for Geometric Graphs
This work addresses a challenging pattern recognition problem for researchers in computational geometry and graph theory, but it is incremental as it modifies existing methods rather than introducing a new paradigm.
The authors tackled the problem of measuring similarity between geometric graphs by adapting two existing distance measures, geometric edit distance (GED) and geometric graph distance (GGD), to ensure they are meaningful and metric in this context, and they proved that computing GGD is NP-hard even for planar graphs.
A geometric graph is a combinatorial graph, endowed with a geometry that is inherited from its embedding in a Euclidean space. Formulation of a meaningful measure of (dis-)similarity in both the combinatorial and geometric structures of two such geometric graphs is a challenging problem in pattern recognition. We study two notions of distance measures for geometric graphs, called the geometric edit distance (GED) and geometric graph distance (GGD). While the former is based on the idea of editing one graph to transform it into the other graph, the latter is inspired by inexact matching of the graphs. For decades, both notions have been lending themselves well as measures of similarity between attributed graphs. If used without any modification, however, they fail to provide a meaningful distance measure for geometric graphs -- even cease to be a metric. We have curated their associated cost functions for the context of geometric graphs. Alongside studying the metric properties of GED and GGD, we investigate how the two notions compare. We further our understanding of the computational aspects of GGD by showing that the distance is $\mathcal{NP}$-hard to compute, even if the graphs are planar and arbitrary cost coefficients are allowed.