Minimum-Complexity Graph Simplification Under the Fréchet-Like Distance

Simplifying granular geometric networks for future computations is vital, especially in geospatial data processing, where maps are frequently used. Given a geometric graph and an error bound, the objective is to compute an alternative graph of a minimum number of vertices and edges in total so that a “Fréchet-like” distance between the two graphs remains at most the error. As curve simplification has a cubic conditional lower bound under the Fréchet distance [9], it seems unlikely to achieve a fast polynomial-time algorithm for graphs under the same distance. In this paper, the Fréchet-like distance we consider between graphs is the “Graph Distance” introduced by Akitaya et al. [3]. Due to its recognized practice in GIS, we assume that the simplified graph is a subgraph of the original graph for which we prove the NP-hardness. Turning our attention to trees, the simplified subtree may not stay connected; hence, we slightly shift the setting to ensure the simplified tree selects its vertices from a subset of the original vertices. We propose two algorithms for tree simplification, including the case where the leaves of the simplified and original trees are mapped and enforced to correspond to one another under the graph distance.