Implementation of Minimum Edge Constraints Sets for Proximity Graphs

For certain edge-constrained proximity algorithms, not every edge of the resulting graph needs to be explicitly stored. This has implications for graph compression. We examine the application and runtime performance on minimum edge-constrained algorithms for three proximity graph types: Delaunay triangulation, Gabriel graph and minimum spanning tree.Implementation details on these algorithms are given, their performance in both large real world datasets and randomized datasets are evaluated. In addition, their compression metrics, the number of edges that are reduced from the constraint edge set, are investigated.